Questo algoritmo per una variazione dello zaino funzionerà? - algoritmo, problema dello zaino

Non sono sicuro di quanta variazione ci sia in realtà, ma ecco il problema:

Stai per partire per un lungo viaggio,prima di farlo è necessario imballare la borsa. Hai una selezione di N elementi che potresti portare avanti. Ogni oggetto ha un peso e un valore che rappresentano quanto utile sarà. Non sarai in grado di trasportare più di K chilogrammi. Qual è il valore totale massimo degli oggetti che puoi portare con? (Puoi avere solo una copia di ogni articolo.)

Ho creato un algoritmo che penso risolverà il problema usando DP, ma non sono sicuro che funzionerà, sarebbe bello se uno di voi desse un'occhiata a questo. Nota: è più come una combinazione di codice psuedo e un algoritmo, non sono neanche sicuro di come scrivere.

Supponendo che k è il peso massimo. Due array: uno contenente il peso di ciascun elemento w [] e l'altro il valore v [].

 for i = 0; i<numberOfItems; i++
{
value = 0
k = MaxWeight;
for(j = i; j<numberOfItems; j++
{
if(j = i)
{
if(k - w[i] >= 0)
{
k = k-w[i]
value = value + v[i]
}
}
else
{
if(k - w[j] >= 0)
{
k = k-w[j]
value = value + v[j]
}
}
}
}

risposte:

No, il tuo avido algoritmo non funziona.

Controlla questo esempio:

MaxWeight = 12
Items = 4 5 4 4 (each value is 1)

Il tuo algoritmo sceglierebbe gli articoli 1 e 2 (o gli articoli 2 e 3, o 3 e 4). La soluzione ottimale è prendere gli articoli 1, 3 e 4.