[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::..]

Originariamente inviato da gugoXX

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

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]

Originariamente inviato da 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

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

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?

[gugoXX]

Originariamente inviato da Tommo

Boh a me pare corretta, almeno per il problema 3

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?

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

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

Ne approfitto per uppare la domanda:

Originariamente inviato da ..::DAVE::..

forse manca ->"di n cifre"?

[cionci]

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

[Johnn]

Originariamente inviato da cionci

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]

Originariamente inviato da ..::DAVE::..

forse manca ->"di n cifre"?

si spera che oltre un certo valore si possano ottenere tutti i successivi

[cionci]

Originariamente inviato da Johnn

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

Originariamente inviato da Vincenzo1968

Questa è la mia soluzione per il contest 11(Problema 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

[marco.r]

Originariamente inviato da 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.

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

[gugoXX]

Originariamente inviato da marco.r

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.