[Vari] Contest 11: Change. NP-Hard.

[gugoXX]

Nella Repubblica di Kobolobo il ministro delle finanze e il direttore della banca centrale sono un po' burloni. Hanno deciso di ritirare tutto il contante dal paese, per far posto al nuovo conio, il kobolo.
Per stimolare la parte matematica dei Kobolobesi, hanno deciso di battere moneta nei seguenti tagli:


5 Koboli
9 Koboli
17 Koboli
30 Koboli
52 Koboli
111 Koboli
209 Koboli






PROBLEMA 1: Quel e' il valore piu' alto che non e' possibile pagare utilizzando un qualsiasi quantitativo di monete tra quelle a disposizione?
Esempi: 6 e 7 non si possono costruire, 14 e' possibile (9+5), 15 e' possibile (5+5+5), 16 non si riesce





PROBLEMA 2: Sia dato in input un file avente il seguente formato:

C1
C2
C3
C4
...
Cn
------------------
T1
T2
T3
...
Tn

Dove C1-Cn sono i valori possibili delle nuove monete battute (Quelli che per l'esercizio 1 erano 5,9,17,30, etc.)
E T1-Tn sono dei prezzi target.
Domanda: Per ciascuno dei prezzi target, trovare una combinazione di monete che possa realizzarlo.
In output e' richiesto un file. Per ciascun prezzo target Tx sara' necessario stampare una riga contenente il valore di ciascun pezzo trovato, separati da +

Esempio:
107 = 30+30+30+17
156 = 52+52+52
111 = 111
16 = N/A (quando non e' possibile realizzarlo)


FILE: http://www.usaupload.net/d/drk0dmnd63s




PROBLEMA 3: La cassiera del supermercato e' molto intelligente. Preferisce muovere il cervello piuttosto che muovere le mani. Ha pertanto deciso che ogni volta che dovra' consegnarci un resto, lo fara' utilizzando il minor numero di monete possibile.
Avendo per esempio a disposizione monete di questo taglio:

1
10
100
105

Dovendoci dare un resto di 112 Koboli
sceglierebbe di darci 4 monete: 100+10+1+1
e non 8 monete: 105+1+1+1+1+1+1+1

Viceversa con un resto da 106 Koboli
sceglierebbe 105+1 (2 monete)
e non 100+5+1 (3 monete)

Dato il file in input del problema 2,
Per ciascuno dei prezzi target trovare il MINIMO NUMERO DI MONETE POSSIBILE e quali monete si devono utilizzare, producendo in output un file analogo a quello del problema 2

Quest'ultimo problema penso che sia un problema NP-Hard, la cui soluzione che non sia forza bruta non e' affatto semplice.
Buon lavoro (e buona fortuna) e complimenti comunque a chiunque voglia avvicinarvisi.

[gugoXX]

Di seguito il codice C# necessario per produrre il file di prova, per futuri utilizzi

class Program
{
static void Main(string[] args)
{
Generator.Generate(@"C:\temp\C11F1.dat", 1000, 100000);
}
}

public static class Generator
{
private static Random rnd = new Random(1567654);


public static void Generate(string FileName, int nValori, int MaxValore)
{
StreamWriter sw = new StreamWriter(FileName);
int[] Coins = new int[] { 5, 9, 17, 30, 52, 111, 209, 500 };
Spool(sw, Coins);
sw.WriteLine("--------------");
Spool(sw, GetRNDList(nValori, MaxValore));
sw.Close();
}

private static IEnumerable<int> GetRNDList(int nValori, int MaxValore)
{
for (int u = 0; u < nValori; u++)
{
yield return rnd.Next(MaxValore);
}
}

private static void Spool(StreamWriter sw, IEnumerable<int> data)
{
data.ForAll(t => sw.WriteLine(t));
}

private static void ForAll<T>(this IEnumerable<T> domain, Action<T> act)
{
domain.ToList().ForEach(act);
}
}

[..::DAVE::..]

PROBLEMA 1: Quel e' il valore piu' alto che non e' possibile pagare utilizzando un qualsiasi quantitativo di monete tra quelle a disposizione?
Esempi: 6 e 7 non si possono costruire, 14 e' possibile (9+5), 15 e' possibile (5+5+5), 16 non si riesce


forse manca ->"di n cifre"?

[Tommo]

Che significa NP e NP-hard?
Sono classificazione della difficoltà?

EDIT:
Boh intanto io ho fatto la versione brute force:


//noteValue contiene l'array dei valori dal piu' grande al piu' piccolo
void decompose( unsigned int targetSum )
{
std::cout << targetSum << " = ";
while( targetSum != 0 )
{
for( unsigned int i = 0; i < noteValuesNb; ++i)
{
if( targetSum >= noteValue[i])
{
targetSum -= noteValue[i];

std::cout << noteValue[i] << " ";
break;
}
}
}
}


Scritta in due secondi ma dovrebbe funzionare... Sicuramente si puo' fare anche senza il for, ma mi sembra una versione decisamente veloce lo stesso...
Fra l'altro questo risolve anche il problema 2, dato che richiede UNA combinazione qualsiasi.

EDIT2:

Un metodo un pò meno brute force, ora va eseguito solo per ogni tipo di banconota. Su somme grosse è molto più veloce del precedente. Nel caso di numeri come 112 invece è meglio usare l'altro, credo.
Io userei l'altro lo stesso, almeno si capisce senza lambiccarsi il cervello :asd:


unsigned int* decompose( unsigned int targetSum )
{
float valueCounted = 0;

unsigned int *times = (unsigned int*)malloc( sizeof( unsigned int ) );

for( unsigned int i = 0; i < noteValuesNb; ++i)
{
times[i] = (unsigned int)( ( targetSum - valueCounted ) / noteValue[i] );
valueCounted += times[i] * noteValue[i];
}
}

[DanieleC88]

Cavoli, bel problema questo... Ci penserò mentre sono via e domani proverò a buttare giù qualche possibile soluzione. ;)

[gugoXX]

Che significa NP e NP-hard?
Sono classificazione della difficoltà?

EDIT:
Boh intanto io ho fatto la versione brute force:


//noteValue contiene l'array dei valori dal piu' grande al piu' piccolo
void decompose( unsigned int targetSum )
{
std::cout << targetSum << " = ";
while( targetSum != 0 )
{
for( unsigned int i = 0; i < noteValuesNb; ++i)
{
if( targetSum >= noteValue[i])
{
targetSum -= noteValue[i];

std::cout << noteValue[i] << " ";
break;
}
}
}
}


Scritta in due secondi ma dovrebbe funzionare... Sicuramente si puo' fare anche senza il for, ma mi sembra una versione decisamente veloce lo stesso...
Fra l'altro questo risolve anche il problema 2, dato che richiede UNA combinazione qualsiasi.

EDIT2:

Un metodo un pò meno brute force, ora va eseguito solo per ogni tipo di banconota. Su somme grosse è molto più veloce del precedente. Nel caso di numeri come 112 invece è meglio usare l'altro, credo.
Io userei l'altro lo stesso, almeno si capisce senza lambiccarsi il cervello :asd:


unsigned int* decompose( unsigned int targetSum )
{
float valueCounted = 0;

unsigned int *times = (unsigned int*)malloc( sizeof( unsigned int ) );

for( unsigned int i = 0; i < noteValuesNb; ++i)
{
times[i] = (unsigned int)( ( targetSum - valueCounted ) / noteValue[i] );
valueCounted += times[i] * noteValue[i];
}
}


Si', sono una catalogazione della complessita' algoritmica.
Con complessita' ascendente abbiamo i
P
NP
NP-hard
NP-complete

Ho idea che tu abbia scritto una soluzione greedy, che non e' detto funzioni ne per il punto 2 ne per il punto 3.
Esempio, con i valori di moneta di test scritti all'inizio, se ti dicessero di comporre 156, quali valori otterresti con il tuo algoritmo?

[Tommo]

Boh a me pare corretta, almeno per il problema 3 :stordita:

Finchè la somma contiene la più grande, usa una di quelle, e così via... mi ci vuole un sacco a mettere su un coso di test, con lettura e scrittura...
sei sicuro che non vada?:stordita:

[gugoXX]

Boh a me pare corretta, almeno per il problema 3 :stordita:

Finchè la somma contiene la più grande, usa una di quelle, e così via... mi ci vuole un sacco a mettere su un coso di test, con lettura e scrittura...
sei sicuro che non vada?:stordita:

Rimetto qui un esempio, cosi' provi a vedere
Immagina di avere come monete le seguenti:

5 Koboli
9 Koboli
17 Koboli
30 Koboli
52 Koboli
111 Koboli
209 Koboli


E ti dicono di comporre il valore 156.

Il tuo algoritmo prende 111 (che e' il piu' grande inferiore)
quindi resta 156-111 = 45
Poi togli 30,
resta 45-30 = 15
poi togli 9
resta 15-9 = 6
poi togli 5
resta 6-5 = 1, rimani li'

Hai ottenuto 111+30+9+5, ovvero 4 monete, e non hai raggiunto il risultato.

Un risultato per il punto 2 poteva essere p.es.
156 = 30+30+30+30+9+9+9+9
Mentre il risultato, ottimo, per il punto 3, doveva essere
156 = 52+52+52

[Tommo]

Oh è vero, hai pienamente ragione :doh:

Ho del tutto sorvolato il fatto che non sempre la migliore combinazione si fa in quel modo...

[Johnn]

Attenzione che 'sta volta si rischia di dimostrare P=NP :asd:

Ne approfitto per uppare la domanda:

forse manca ->"di n cifre"?

[cionci]

Con un algoritmo genetico sarebbe fattibile, è un po' un problema la ricombinazione :(

[Johnn]

Con un algoritmo genetico sarebbe fattibile, è un po' un problema la ricombinazione :(

Non sono particolarmente ferrato sugli algoritmi genetici, ma non è un'euristica? Hai la garanzia di trovare la soluzione ottima?

[Furla]

forse manca ->"di n cifre"?
si spera che oltre un certo valore si possano ottenere tutti i successivi ;)

[cionci]

Non sono particolarmente ferrato sugli algoritmi genetici, ma non è un'euristica? Hai la garanzia di trovare la soluzione ottima?
Non la hai, ma per il problema 2 è perfetto.

[wingman87]

E' un problema sullo stile di quello dello zaino vero? Non sono mai stato bravo in questo genere di problemi ma vorrei imparare a risolverli, appena ho del tempo mi cimento anche io :)

[VICIUS]

439 è la risposta giusta al primo quesito? Purtroppo mi è uscita una funzione ricorsiva e con numeri oltre le 5 cifre non ho abbastanza stack. Il codice è questo:
def brute_force(money, i, coins)
return false if i == coins.size

i += 1 while (coins[i] > money) and (i+1 < coins.size)

money -= coins[i]

return false if money < 0
return true if money == 0

if not brute_force(money, i, coins)
brute_force(money+coins[i], i+1, coins)
else
return true
end
end

def remove_multiples_from_list(n, list)
n.step(list.size, n) do |i|
list[i] = nil
end
end


def contest_10(len, coins)
list = Array.new(('9'*len).to_i)
for i in 0..list.size
list[i] = i
end

for i in 1..coins.size
coins.combination(i).each do |c|
t = c.inject {|tot, x| tot += x}
remove_multiples_from_list(t, list)
end
end

list.compact!

i = list.size - 1
i -= 1 while brute_force(list[i], 0, coins)
list[i]
end

coins = [209, 111, 52, 30, 17, 9, 5]
puts contest_10(5, coins)

[gugoXX]

Mi sa di no.
439 = 9+ 5*86

Comunque quel cabasiso di Vincenzo ha trovato in una biblioteca segreta la soluzione al quesito 3 (e quindi anche al 2) e l'ha realizzata come sempre in C.

Mi piacerebbe vedere soluzioni Naive, che possano dare i risultati corretti anche se non per forza realizzati con un algoritmo ottimo (PS: Essendo NP-Hard non e' dimostrabile che un algoritmo, sebbene dia i risultati corretti, sia quello ottimo).
Diciamo soluzioni "nuove", non realizzate con algoritmi noti.
P.es. il tuo approccio Vicius mi piace.

[gugoXX]

In Behalf of Vincenzo


Questa è la mia soluzione per il contest 11(Problema 3):

http://www.guidealgoritmi.it/images/ImgForums/Contest11CSoluz.jpg


AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional (32 bit)
Service Pack 3



#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <malloc.h>

#define BUFFER_SIZE 4096

#define ARRAY_SIZE(Array) (sizeof(Array) / sizeof((Array)[0]))

typedef enum tagStati
{
S_ERROR = -1, S0 = 0, S1, S2, S3, S4, S5, S6, S7, S8, S9
} Stati;

void ComputeChange(int *d, int k, int n, int *C, int *S)
{
int j, i;

for( j = 1; j <= n; j++ )
{
C[j] = 1000000000;
for ( i = 1; i <= k; i++ )
{
if ( j >= d[i] && 1 + C[j - d[i]] < C[j] )
{
C[j] = 1 + C[j - d[i]];
S[j] = d[i];
}
}
}
}

void GiveChange(int j, int *S)
{
if ( S[j] == 0 )
return;

while ( j > 0 )
{
printf("S[%d] -> %d\n", j, S[j]);
j = j - S[j];
}
}

int CountDenoms(const char *szFileName)
{
FILE *fp;
unsigned char buffer[BUFFER_SIZE];
int numread;
int k;
int count;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

k = 0;
numread = fread(buffer, 1, BUFFER_SIZE, fp);
while ( k < numread )
{
if ( *(buffer + k) == '\n' )
count++;
if ( *(buffer + k) == '-' )
break;
++k;
}

fclose(fp);

return count;
}

Stati DFA(const char *szFileName)
{
Stati stato = S0;
FILE *fp, *fpOut;
unsigned char buffer[BUFFER_SIZE];
char output[4096];
char szTemp[4096];
int numblocks;
int numread;
unsigned char c;
int k, x, j;
int riga;
char szNum[256];
int num;

int *denoms = NULL;
int countDenoms;
int index;

int *C = NULL;
int *S = NULL;

unsigned char byteCR = 0xD; // Carriage Return
unsigned char byteLF = 0xA; // Line Feed

C = (int*)malloc(sizeof(int)*1000000);
if ( !C )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

S = (int*)malloc(sizeof(int)*1000000);
if ( !S )
{
printf("Memoria insufficiente.\n");
free(C);
return S_ERROR;
}

countDenoms = CountDenoms(szFileName);
denoms = (int*)malloc(sizeof(int)*countDenoms + 1);
if ( !denoms )
{
printf("Memoria insufficiente.\n");
free(C);
free(S);
return S_ERROR;
}
denoms[0] = 0;
index = 1;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
free(C);
free(S);
free(denoms);
return S_ERROR;
}

fpOut = fopen("Output.txt", "wb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file Output.txt\n");
fclose(fp);
free(C);
free(S);
free(denoms);
return S_ERROR;
}

if ( fseek(fp, 0, SEEK_END) )
return 0;

numblocks = ftell(fp)/BUFFER_SIZE;
if ( numblocks == 0 )
{
numblocks = 1;
}
else
{
if ( ftell(fp) % BUFFER_SIZE != 0 )
numblocks++;
}

fseek(fp, 0, SEEK_SET);
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 1 nella lettura del file %s\n", szFileName);
free(C);
free(S);
free(denoms);
return S_ERROR;
}

num = 0;
k = x = j = 0;
riga = 1;
while ( x < numblocks )
{
c = *(buffer + k++);

if ( c == byteLF )
{
riga++;
}

switch (stato)
{
case S0:
if ( c >= '0' && c <= '9' )
{
szNum[j++] = c;
}
else if ( c == byteLF )
{
szNum[j] = '\0';
denoms[index++] = atoi(szNum);
j = 0;
}
else if ( c == '-' )
{
while ( c != byteLF )
{
c = *(buffer + k++);
if ( k >= numread )
break;
}
stato = S1;
}
else if ( c == byteCR )
{
// nada
}
else
{
printf("Errore: stato S0; riga %d\n", riga);
fclose(fp);
fclose(fpOut);
free(C);
free(S);
free(denoms);
return S_ERROR;
}
break;

case S1:
if ( c >= '0' && c <= '9' )
{
szNum[j++] = c;
}
else if ( c == byteCR )
{
// nada
}
else if ( c == byteLF )
{
szNum[j] = '\0';
num = atoi(szNum);
j = 0;

ComputeChange(denoms, countDenoms, num, C, S);

strcpy(output, szNum);
strcat(output, " = ");
if ( S[num] > 0 )
{
while ( num > 0 )
{
sprintf(szTemp, "%d", S[num]);
strcat(output, szTemp);
strcat(output, "+");
num = num - S[num];
}
output[strlen(output) - 1] = '\0';
}
else
{
strcat(output, "N/A");
}
fwrite(output, strlen(output), 1, fpOut);
fwrite(&byteCR, 1, 1, fpOut);
fwrite(&byteLF, 1, 1, fpOut);
}
else
{
printf("Errore: stato S1; riga %d\n", riga);
fclose(fp);
fclose(fpOut);
free(C);
free(S);
free(denoms);
return S_ERROR;
}
break;
}

if ( k >= numread )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
k = 0;
x++;
}
}

fclose(fp);
fclose(fpOut);

free(C);
free(S);
free(denoms);

return stato;
}

int main()
{
Stati stato;
clock_t c_start, c_end;

char *szFileName = "C11F1.dat";

c_start = clock();
stato = DFA(szFileName);
c_end = clock();
printf("\nCreato il file output.txt\n");
printf("\nTempo impiegato -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

return 0;
}


Me la puoi postare(compresi macchina e tempi), please :)

:bimbo:

[marco.r]

Mi sa di no.
439 = 9+ 5*86

Comunque quel cabasiso di Vincenzo ha trovato in una biblioteca segreta la soluzione al quesito 3 (e quindi anche al 2) e l'ha realizzata come sempre in C.

Mi piacerebbe vedere soluzioni Naive, che possano dare i risultati corretti anche se non per forza realizzati con un algoritmo ottimo (PS: Essendo NP-Hard non e' dimostrabile che un algoritmo, sebbene dia i risultati corretti, sia quello ottimo).
Diciamo soluzioni "nuove", non realizzate con algoritmi noti.
P.es. il tuo approccio Vicius mi piace.

Non occorre una biblioteca segreta, mi sembra sia un problema abbastanza standard. Se si vogliono algoritmi originali, bisogna proporre problemi originali :P.

[gugoXX]

Non occorre una biblioteca segreta, mi sembra sia un problema abbastanza standard. Se si vogliono algoritmi originali, bisogna proporre problemi originali :P.

Eh lo so.
Ma poiche' penso (pensavo) che non tutti conoscessero la programmazione dinamica, e soprattutto come riuscire a costruire un nuovo algoritmo dinamico dato uno specifico problema, speravo che potesse venire fuori qualcosa di interessante.

[Johnn]

Mi sa di no.
439 = 9+ 5*86


Confermo. Non è 439.

Eh lo so.
Ma poiche' penso (pensavo) che non tutti conoscessero la programmazione dinamica, e soprattutto come riuscire a costruire un nuovo algoritmo dinamico dato uno specifico problema, speravo che potesse venire fuori qualcosa di interessante.

Volendo si può approcciare con questo tipo di problemi in modo molto creativo... E ciò può portare, in generale, ad algoritmi più performanti nella pratica (rimanendo sempre con complessità esponenziale nel caso peggiore, ovviamente).

[DanieleC88]

Ma poiche' penso (pensavo) che non tutti conoscessero la programmazione dinamica [...]
Eccomi, sono ignorante nel campo. :D

[marco.r]

Eh lo so.
Ma poiche' penso (pensavo) che non tutti conoscessero la programmazione dinamica, e soprattutto come riuscire a costruire un nuovo algoritmo dinamico dato uno specifico problema, speravo che potesse venire fuori qualcosa di interessante.
No problem, non voleva essere una critica nei tuoi confronti, in fondo sei quello che perde tempo a cercare i quesiti :P. In teoria nei prossimi giorni saro' un po' piu' libero, per cui spero di riuscire a proporre un qualcosa di meno noto e forse un po' piu' giocoso... devo solo trovare il tempo per scrivere un po' di codice di contorno.
Per inciso il primo punto mi sembra un po' meno standard... nel senso che forse si riesce a ricavare qualcosa di piu' veloce che non la semplice programmazione dinamica....

[VICIUS]

Mi sa di no.
439 = 9+ 5*86
Mi sono accorto ora che mancava un pezzo... :muro: Questa volta la risposta sembra essere 21. È corretta?

Comunque quel cabasiso di Vincenzo ha trovato in una biblioteca segreta la soluzione al quesito 3 (e quindi anche al 2) e l'ha realizzata come sempre in C.
Il programma di Vincenzo non mi funziona sul imac di casa. L'ho provato per 5 minuti e non ho ottenuto nessun output. L'unica modifica che ho fatto è cancellare l'include a malloc.h perché su osx quel file non esiste.

In ogni caso mi sembra strano che ci metta due secondi per generare l'output. La mia funzione brute force non salva i valori per l'output e probabilmente è sbaglio qualcosa ma finisce la ricerca del file .dat in 56 millisecondi.

[VICIUS]

Il programma di Vincenzo non mi funziona sul imac di casa. L'ho provato per 5 minuti e non ho ottenuto nessun output. L'unica modifica che ho fatto è cancellare l'include a malloc.h perché su osx quel file non esiste.
Come non detto. Funziona ma per qualche motivo è lentissimo.
Creato il file output.txt

Tempo impiegato -> 519.80278 secondi

[banryu79]

Come richiestomi da Vincenzo, ho mandato in esecuzione il suo algoritmo sulla mia macchina e questi sono i risultati ottenuti:

http://img296.imageshack.us/img296/1130/runresultye1.jpg (http://imageshack.us)

su questa macchina:

http://img212.imageshack.us/img212/8828/macchinaou8.jpg (http://imageshack.us)

[Tommo]

Ho testato anche io il programma di Vincenzo1968:


Creato il file output.txt

Tempo impiegato -> 2.57300 secondi


Su un E6600 2.4Ghz + 2gb + Vista non troppo in idle...

In effetti 517 secondi mi pare un tantino un'esagerazione :asd:

[banryu79]

Vincenzo mi chiede anche di precisare che l'algortimo usato non è suo ma l'ha trovato con una ricerca su gugol.
Mi ha pregato di postare la fonte: http://oucsace.cs.ohiou.edu/~razvan/.../lecture19.pdf

[Johnn]

Vincenzo mi chiede anche di precisare che l'algortimo usato non è suo ma l'ha trovato con una ricerca su gugol.
Mi ha pregato di postare la fonte: http://oucsace.cs.ohiou.edu/~razvan/.../lecture19.pdf

Il link non va: ci sono i puntini in mezzo. :D

[cionci]

http://oucsace.cs.ohiou.edu/~razvan/courses/cs404/lecture19.pdf

[gugoXX]

Getto qui la mia per il punto 3
Ovviamente in Programmazione dinamica anche qui.


Read in 1ms
Found all the minimum change of the 1000 Targets in 250ms
Output in 31ms




class Program
{
static void Main(string[] args)
{
//Generator.Generate(@"C:\temp\C11F1.dat", 1000, 100000);

Stopwatch swatch = new Stopwatch();
swatch.Start();
Data dt = new Data();
dt.Load(@"C:\temp\C11F1.dat");

long inputtime = swatch.ElapsedMilliseconds;

int mtarg = dt.Targets.Max();

Composer cmp = new Composer(dt.Coins,mtarg);
long interm = swatch.ElapsedMilliseconds;

StreamWriter sw = new StreamWriter(@"C:\temp\C11Out.dat");
string[] CoinsString = dt.Coins.Select(t => t.ToString()).ToArray();
foreach (int d in dt.Targets)
{
sw.Write("{0} = ", d);
Token tk=cmp.Minimum[d];
if (tk == null) sw.WriteLine("N/A");
else sw.WriteLine(tk.ToString(CoinsString));
}
sw.Close();
swatch.Stop();
Console.WriteLine("Read in {0}ms", inputtime);
Console.WriteLine("Found all the minimum change of the {0} Targets in {1}ms", dt.Targets.Length, interm-inputtime);
Console.WriteLine("Output in {0}ms", swatch.ElapsedMilliseconds-interm);
Console.ReadKey();
}
}

public class Data
{
public int[] Coins;
public int[] Targets;

public void Load(string filename)
{
StreamReader sr = new StreamReader(filename);
string line;

List<int> cns = new List<int>();
while (!(line=sr.ReadLine()).StartsWith("-"))
{
cns.Add(int.Parse(line));
}

List<int> tgs = new List<int>();
while((line=sr.ReadLine())!=null)
{
tgs.Add(int.Parse(line));
}

sr.Close();

Coins = cns.ToArray();
Targets = tgs.ToArray();
}
}

public class Token
{
public int[] Mult;

public int NCoins
{
get
{
return Mult.Sum();
}
}

public int this[int n]
{
get
{
return Mult[n];
}
set
{
Mult[n] = value;
}
}

public Token(int n)
{
Mult = new int[n];
}

public Token(Token cp)
{
Mult = cp.Mult.ToArray();
}

public string ToString(string[] Coins)
{
List<string> str = new List<string>();
for (int t = 0; t < Mult.Length; t++)
{
int na = Mult[t];
string coin = Coins[t];
for (int u = 0; u < na; u++)
{
str.Add(coin);
}
}
string[] strs=str.ToArray();
return string.Join("+", strs);
}
}

public class Composer
{
int[] Coins;

public Token[] Minimum = null;

public Composer(int[] p_Coins,int maxVal)
{
Coins = p_Coins.OrderBy(t => t).ToArray();
maxVal++;
int clen = Coins.Length;
Minimum = new Token[maxVal];

//Prepare
for (int t = 0; t < clen; t++)
{
int coin = Coins[t];
Token tk = new Token(clen);
tk[t] = 1;
Minimum[coin] = tk;
}

//Dynamic. Complexity O(n*m) (Pseudopolynomial)
for (int t = Coins[0]*2; t < maxVal; t++)
{
if (Minimum[t] != null) continue;
int cminl = int.MaxValue;
for (int u = 0; u < clen; u++)
{
int coin = Coins[u];
int back = t - coin;
if (back < 0) break;

Token TokenBack = Minimum[back];

if (TokenBack != null)
{
int tbkl = TokenBack.NCoins;
if (tbkl < (cminl - 1))
{
Token tk = Minimum[t] = new Token(TokenBack);
tk[u]++;
cminl = tbkl+1;
}
}
}
}
}
}

[Johnn]

http://oucsace.cs.ohiou.edu/~razvan/courses/cs404/lecture19.pdf

Grazie.


Ho compilato il sorgente di vincenzo sotto linux con questa config:

gcc versione 4.2.4
cpu: intel centrino 1,5 Ghz
768 Mb di ram 333
governor: performance (l'equivalente di alte prestazioni, processore sempre al massimo della frequenza)

Questo è l'output della compilazione con comando "gcc Contest11C.c":

Contest11C.c: In function 'DFA':
Contest11C.c:244: warning: incompatible implicit declaration of built-in function 'strcpy'
Contest11C.c:245: warning: incompatible implicit declaration of built-in function 'strcat'
Contest11C.c:255: warning: incompatible implicit declaration of built-in function 'strlen'
Contest11C.c:261: warning: incompatible implicit declaration of built-in function 'strlen'
Contest11C.c:330:2: warning: no newline at end of file

Questo è l'output:

Creato il file output.txt

Tempo impiegato -> 7.55000 secondi

Con opzione di ottimizzazione:
-O2
Creato il file output.txt

Tempo impiegato -> 3.52000 secondi


Con -O3 i tempi sono praticamente gli stessi.

Il file generato è di 405,8 Kbyte.

[DanieleC88]

Ho provato il programma di Vincenzo e gli ho segnalato un errore, mi ha chiesto di postarvi il resoconto qui, quindi incollo il mio messaggio:
Ciao Vincenzo,
ho provato il tuo programma sulla mia macchina (da Linux) e ho trovato un piccolo bug: la variabile count in CountDenoms() non era inizializzata, ma veniva incrementata dopo e restituita alla chiamante. All'inizio, prima di trovare questo errore, il programma continuava a fallirmi per “Memoria insufficiente”, evidentemente il valore iniziale della variabile era interpretato come un intero molto grande, e la malloc() falliva. Probabilmente è anche per questo motivo che a VICIUS (che probabilmente starà usando anche lui GCC) veniva un'allocazione sballata e una zona di memoria improbabilmente grande, dando origine ad un tempo di esecuzione sproporzionato. :D

Quasi dimenticavo: termina correttamente dopo 7.23 secondi sulla mia macchina.

Il mio sistema è questo:
[jmc@mordor Contest 11]$ cat /proc/cpuinfo
processor : 0
vendor_id : AuthenticAMD
cpu family : 6
model : 4
model name : AMD Athlon(tm) Processor
stepping : 2
cpu MHz : 1002.258
cache size : 256 KB
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 1
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 sep mtrr pge mca cmov pat pse36 mmx fxsr syscall mmxext 3dnowext 3dnow up
bogomips : 2005.03
clflush size : 32
power management:

[jmc@mordor Contest 11]$ uname -a
Linux mordor 2.6.27-ARCH #1 SMP PREEMPT Mon Dec 8 22:01:01 UTC 2008 i686 AMD Athlon(tm) Processor AuthenticAMD GNU/Linux
Il programma era compilato con -W -Wall -O3.

[VICIUS]

Non è nemmeno il count non inizializato. Penso sia un bug dei gcc perché su windows funziona bene. :)

[Johnn]

Ho provato il programma di Vincenzo e gli ho segnalato un errore, mi ha chiesto di postarvi il resoconto qui, quindi incollo il mio messaggio:

Il programma era compilato con -W -Wall -O3.

Che versione di gcc usi?

Hai provato con -O2?

[DanieleC88]

Non è nemmeno il count non inizializato. Penso sia un bug dei gcc perché su windows funziona bene. :)
Che versione hai di GCC? Io ho questa:
[jmc@mordor ~]$ gcc -v
Using built-in specs.
Target: i686-pc-linux-gnu
Configured with: ../configure --prefix=/usr --enable-shared --enable-languages=c,c++,fortran,objc,obj-c++,treelang --enable-threads=posix --mandir=/usr/share/man --infodir=/usr/share/info --enable-__cxa_atexit --disable-multilib --libdir=/usr/lib --libexecdir=/usr/lib --enable-clocale=gnu --disable-libstdcxx-pch --with-tune=generic
Thread model: posix
gcc version 4.3.2 (GCC)

[VICIUS]

Che versione hai di GCC? Io ho questa:
[jmc@mordor ~]$ gcc -v
Using built-in specs.
Target: i686-pc-linux-gnu
Configured with: ../configure --prefix=/usr --enable-shared --enable-languages=c,c++,fortran,objc,obj-c++,treelang --enable-threads=posix --mandir=/usr/share/man --infodir=/usr/share/info --enable-__cxa_atexit --disable-multilib --libdir=/usr/lib --libexecdir=/usr/lib --enable-clocale=gnu --disable-libstdcxx-pch --with-tune=generic
Thread model: posix
gcc version 4.3.2 (GCC)
4.0.1 e 4.2.1

[Vincenzo1968]

Getto qui la mia per il punto 3
Ovviamente in Programmazione dinamica anche qui.


Read in 1ms
Found all the minimum change of the 1000 Targets in 250ms
Output in 31ms




class Program
{
static void Main(string[] args)
{
//Generator.Generate(@"C:\temp\C11F1.dat", 1000, 100000);

Stopwatch swatch = new Stopwatch();
swatch.Start();
Data dt = new Data();
dt.Load(@"C:\temp\C11F1.dat");

long inputtime = swatch.ElapsedMilliseconds;

int mtarg = dt.Targets.Max();

Composer cmp = new Composer(dt.Coins,mtarg);
long interm = swatch.ElapsedMilliseconds;

StreamWriter sw = new StreamWriter(@"C:\temp\C11Out.dat");
string[] CoinsString = dt.Coins.Select(t => t.ToString()).ToArray();
foreach (int d in dt.Targets)
{
sw.Write("{0} = ", d);
Token tk=cmp.Minimum[d];
if (tk == null) sw.WriteLine("N/A");
else sw.WriteLine(tk.ToString(CoinsString));
}
sw.Close();
swatch.Stop();
Console.WriteLine("Read in {0}ms", inputtime);
Console.WriteLine("Found all the minimum change of the {0} Targets in {1}ms", dt.Targets.Length, interm-inputtime);
Console.WriteLine("Output in {0}ms", swatch.ElapsedMilliseconds-interm);
Console.ReadKey();
}
}

public class Data
{
public int[] Coins;
public int[] Targets;

public void Load(string filename)
{
StreamReader sr = new StreamReader(filename);
string line;

List<int> cns = new List<int>();
while (!(line=sr.ReadLine()).StartsWith("-"))
{
cns.Add(int.Parse(line));
}

List<int> tgs = new List<int>();
while((line=sr.ReadLine())!=null)
{
tgs.Add(int.Parse(line));
}

sr.Close();

Coins = cns.ToArray();
Targets = tgs.ToArray();
}
}

public class Token
{
public int[] Mult;

public int NCoins
{
get
{
return Mult.Sum();
}
}

public int this[int n]
{
get
{
return Mult[n];
}
set
{
Mult[n] = value;
}
}

public Token(int n)
{
Mult = new int[n];
}

public Token(Token cp)
{
Mult = cp.Mult.ToArray();
}

public string ToString(string[] Coins)
{
List<string> str = new List<string>();
for (int t = 0; t < Mult.Length; t++)
{
int na = Mult[t];
string coin = Coins[t];
for (int u = 0; u < na; u++)
{
str.Add(coin);
}
}
string[] strs=str.ToArray();
return string.Join("+", strs);
}
}

public class Composer
{
int[] Coins;

public Token[] Minimum = null;

public Composer(int[] p_Coins,int maxVal)
{
Coins = p_Coins.OrderBy(t => t).ToArray();
maxVal++;
int clen = Coins.Length;
Minimum = new Token[maxVal];

//Prepare
for (int t = 0; t < clen; t++)
{
int coin = Coins[t];
Token tk = new Token(clen);
tk[t] = 1;
Minimum[coin] = tk;
}

//Dynamic. Complexity O(n*m) (Pseudopolynomial)
for (int t = Coins[0]*2; t < maxVal; t++)
{
if (Minimum[t] != null) continue;
int cminl = int.MaxValue;
for (int u = 0; u < clen; u++)
{
int coin = Coins[u];
int back = t - coin;
if (back < 0) break;

Token TokenBack = Minimum[back];

if (TokenBack != null)
{
int tbkl = TokenBack.NCoins;
if (tbkl < (cminl - 1))
{
Token tk = Minimum[t] = new Token(TokenBack);
tk[u]++;
cminl = tbkl+1;
}
}
}
}
}
}


Ohé Gugo,

in primis complimenti per la tua soluzione. Ho provato con un file dieci volte più grosso e i tempi rimangono uguali(circa 300ms sia per la versione sul file piccolo che per quella sul file grosso).
Ma come cavolo (http://it.wikisource.org/wiki/Sonetti_romaneschi/Er_padre_de_li_Santi) hai fatto?

Adesso devi spiegarci l'algoritmo. E avrei anche una domanda sul C#: io sono rimasto fermo alla vecchia versione.

In questa riga di codice:


string[] CoinsString = dt.Coins.Select(t => t.ToString()).ToArray();


che significa '=>'? È un nuovo operatore?

Grazie ;)

:bimbo:

[gugoXX]

Ohé Gugo,

in primis complimenti per la tua soluzione. Ho provato con un file dieci volte più grosso e i tempi rimangono uguali(circa 300ms sia per la versione sul file piccolo che per quella sul file grosso).
Ma come cavolo (http://it.wikisource.org/wiki/Sonetti_romaneschi/Er_padre_de_li_Santi) hai fatto?

Adesso devi spiegarci l'algoritmo. E avrei anche una domanda sul C#: io sono rimasto fermo alla vecchia versione.

In questa riga di codice:


string[] CoinsString = dt.Coins.Select(t => t.ToString()).ToArray();


che significa '=>'? È un nuovo operatore?

Grazie ;)

:bimbo:

L'operatore => e' l'operatore di proiezione.
Quella riga li' si legge:
Presa dt.Coins come collezione delle monete
.Select = Vogliamo trasformarla in un'altra collezione
(t=> = Chiamato t la singola moneta
t.toString() = Restituisci la stringa relativa alla stampa della moneta (Quindi l'intero trasformato in stringa decimale)
).ToArray() = e la collezione finale finalizzala in un array (di stringhe ovviamente)

Per la spiegazione dell'algoritmo occorre addentrarsi un minimo nella programmazione dinamica e nella complessita' algoritmica.
La programmazione dinamica e' utile per cercare di risolvere i problemi di tipo NP-Hard, ovvero quei tipi di problemi per cui si ha talvolta la possibilita' di scrivere un algoritmo che si puo' ridurre ad un problema di tipo NP-Completo in tempo polinomiale.
A sua volta i problemi NP-completi sono i problemi piu' difficili della classe P - NP, dove per NP (che sta per non-deterministic polinomial), si intendono i problemi che non si possono risolvere in tempo polinomiale giocando solo con il numero degli elmenti di input.
Con la programmazione dinamica e' pero' possibile alcune volte riuscire a scrivere un algoritmo pesudo-polinomiale per la soluzione dei problemi NP-Completi, e quindi anche di alcuni degli NP-Hard.

Cosa significa polinomiale, non-polinomiale o pesudo-polinomiale in questo senso:
- Polinomiale: dati gli elementi di ingresso, esiste un algoritmo con complessita' polinomiale in grado di risolvere la domanda, che sia funzione unicamente del numero dei dati in ingresso.
- Non-Polinomiale: Dati gli elementi in ingresso esiste un algoritmo esponenziale in grado di risolvere la domanda, che sia funzione del numero dei dati in ingresso
- Pseudo-Polinomiale: Dati gli elementi in ingresso, esiste un algoritmo polinomiale in grado di risolvere la domanda, che sia funzione del numero dei dati di ingresso e di qualche altro fattore (tipicamente moltiplicativo).

Nel nostro caso, se esistesse un algorimto polinomiale per dire:
dato 100.000 come valore da cambiare, e dati 5 monete con il loro valore, tale algoritmo dovrebbe riuscire ad enunciare la soluzione di cambio con il minor numero di monete possibili in un tempo O(5), oppure O(5^2), oppure O(5^3), con eventuali fattori moltiplicativi dipendenti dalla soluzione trovata, e non da altri fattori.
Ebbene, non e' possibile (meglio, non e' ancora dimostrata la riduzione o la non-riduzione dei problemi da NP a P. E' uno dei problemi del millennio)
E' possibile trovare la soluzione sicuramente pero' enumerando tutti i possibili insiemi di monete, in tempo esponenziale (forza bruta)

Con la programmazione dinamica e' pero' possibile trovare la soluzione ottima in un tempo inferiore a O(N*m) = O(5 * 100.000), dove 5 e' il numero di monete e 100.000 e' uno dei valori del problema.
Un po' come se per problemi tipo "Calcolare la distanza minima tra tutti i punti dati", nella complessita' dell'algoritmo centrassero anche i valori delle coordinate dei punti. Cosa che in realta' non e'.

E il tuo algoritmo e' proprio di questo tipo.
Dato un valore come 100.000, si avvicina a 100.000 cercando e trovando la soluzione ottima per alcuni dei valori inferiori a 100.000. Diciamo che la complessita' sia O(n*M/s) = O (5 * 100.000 / s) dove s e' la ratio media di quante soluzioni ottime dovra' trovare, rispetto al totale da 100.000, per costruire poi finalmente la soluzione da 100.000.
Il "di quali altri valori intermedi" si ha bisogno della soluzione ottima, per poi arrivare al nostro 100.000 e' tutto insito nella logica dell'algoritmo dinamico.
Tali algoritmi sono parecchio difficili da trovare, come quelli dello zaino unbounded, o come il commesso viaggiatore senza limiti (ovvero toccare tutte le citta', pur anche ritoccando ogni citta' quante volte si vuole, purche' si faccia pero' il percorso minimo, che e' proprio quello che il postino vuole).

Quelli meno difficili da trovare sono le soluzioni "forza bruta" degli algoritmi dinamici. In pratica cercando la soluzione ottima di tutti i sottoproblemi compresi tra 1 e 100.000. In pratica quando la soluzione non e' inferiore a O(N*M), ma e' proprio N*M (ovvero come il tuo quando s = 1)
Nel mio algoritmo infatti ho cercato tutte le soluzioni di tutti i possibili valori compresi tra 1 e il massimo richiesto. Tale sarebbe stato lo "sforzo" per trovare la soluzione di quell'unico preciso valore.
Ma per costruzione, cosi' facendo ho trovato anche la soluzione di tutti i valori intermedi, e mi e' bastato memorizzarli per spararli fuori al momento dell'output... l'ottimizzazione sta qui.

Il mio algoritmo e' peggiore di quello da te trovato perche' calcola la soluzione ottima di tanti altri valori non richiesti.
Ma cosi' facendo nel complesso e' migliore, perche' l'ho richiamato una sola volta...

Certo, se il valore massimo fosse 2.000.000.000, allora il mio algoritmo diventa vecchio, mentre il tuo forse ancora decente :D

[banryu79]

... snip ...

Ho capito tutta la spiegazione :idea:
Grazie GugoXX, sei stato illuminante.


L'operatore => e' l'operatore di proiezione.
Quella riga li' si legge:
Presa dt.Coins come collezione delle monete
.Select = Vogliamo trasformarla in un'altra collezione
(t=> = Chiamato t la singola moneta
t.toString() = Restituisci la stringa relativa alla stampa della moneta (Quindi l'intero trasformato in stringa decimale)
).ToArray() = e la collezione finale finalizzala in un array (di stringhe ovviamente)

Fico :sbav:

[Vincenzo1968]

...
Quelli meno difficili da trovare sono le soluzioni "forza bruta" degli algoritmi dinamici. In pratica cercando la soluzione ottima di tutti i sottoproblemi compresi tra 1 e 100.000. In pratica quando la soluzione non e' inferiore a O(N*M), ma e' proprio N*M (ovvero come il tuo quando s = 1)
Nel mio algoritmo infatti ho cercato tutte le soluzioni di tutti i possibili valori compresi tra 1 e il massimo richiesto. Tale sarebbe stato lo "sforzo" per trovare la soluzione di quell'unico preciso valore.
Ma per costruzione, cosi' facendo ho trovato anche la soluzione di tutti i valori intermedi, e mi e' bastato memorizzarli per spararli fuori al momento dell'output... l'ottimizzazione sta qui.

Il mio algoritmo e' peggiore di quello da te trovato perche' calcola la soluzione ottima di tanti altri valori non richiesti.
Ma cosi' facendo nel complesso e' migliore, perche' l'ho richiamato una sola volta...

Certo, se il valore massimo fosse 2.000.000.000, allora il mio algoritmo diventa vecchio, mentre il tuo forse ancora decente :D

Grazie mille :)
Se ho capito bene(ho lacune spaventose in matematica) calcoli tutte le soluzioni per i valori da 1 a 100.000 e le memorizzi in una sorta di hashtable. E così si spiega anche il fatto che il tempo di esecuzione si mantenga costante anche con un file dieci volte più grosso. Giusto?

[gugoXX]

Grazie mille :)
Se ho capito bene(ho lacune spaventose in matematica) calcoli tutte le soluzioni per i valori da 1 a 100.000 e le memorizzi in una sorta di hashtable. E così si spiega anche il fatto che il tempo di esecuzione si mantenga costante anche con un file dieci volte più grosso. Giusto?

Si', esatto. Cambierebbe se ampliassi il range oltre 100.000
Invece il tuo algoritmo per ciascuno dei valori N trova la soluzione ottima, senza pero' calcolare tutti i possibili 1-N, ma solo qualcuno per questo e', nel singolo, piu' efficiente (e piu' difficile da studiare)

[Vincenzo1968]

Si', esatto. Cambierebbe se ampliassi il range oltre 100.000
Invece il tuo algoritmo per ciascuno dei valori N trova la soluzione ottima, senza pero' calcolare tutti i possibili 1-N, ma solo qualcuno per questo e', nel singolo, piu' efficiente (e piu' difficile da studiare)

Ahò,

è gajiarda com'idea. Vojio provà a implementalla in C.

:bimbo:

[Vincenzo1968]

L'operatore => e' l'operatore di proiezione.
Quella riga li' si legge:
Presa dt.Coins come collezione delle monete
.Select = Vogliamo trasformarla in un'altra collezione
(t=> = Chiamato t la singola moneta
t.toString() = Restituisci la stringa relativa alla stampa della moneta (Quindi l'intero trasformato in stringa decimale)
).ToArray() = e la collezione finale finalizzala in un array (di stringhe ovviamente)
...


Parliamo di Lambda Expressions, giusto?

:bimbo:

[gugoXX]

Parliamo di Lambda Expressions, giusto?

:bimbo:

Si' esatto, sono le Lambda expression.