Wird dieser Algorithmus für eine Variante des Rucksacks funktionieren? - Algorithmus, Rucksack-Problem

Ich bin nicht sicher, wie viel Variation es tatsächlich ist, aber hier ist das Problem:

Du bist dabei, eine lange Reise zu machen,Bevor Sie das tun, müssen Sie Ihre Tasche packen. Sie haben eine Auswahl von N Elementen, die Sie mitnehmen können. Jedes Element hat ein Gewicht und einen Wert, der angibt, wie nützlich es sein wird. Sie können nicht mehr als K Kilogramm tragen. Was ist der maximale Gesamtwert der Gegenstände, die du mitnehmen kannst? (Sie können nur eine Kopie jedes Artikels haben.)

Ich habe einen Algorithmus erstellt, von dem ich denke, dass er das Problem mit DP lösen wird, aber ich bin mir nicht sicher, ob es funktionieren wird, es wäre großartig, wenn einer von euch einen Blick darauf werfen würde. Hinweis: Es ist mehr wie eine Kombination aus Pseudo-Code und einem Algorithmus, ich bin mir nicht sicher, wie man beides schreibt.

Angenommen, k ist das maximale Gewicht. Zwei Arrays: eines mit dem Gewicht jedes Elements w [] und das andere mit dem Wert 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]
}
}
}
}

Antworten:

Nein, dein gieriger Algorithmus wird nicht funktionieren.

Überprüfen Sie dieses Beispiel:

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

Ihr Algorithmus würde Elemente 1 und 2 (oder Elemente 2 und 3 oder 3 und 4) auswählen. Optimale Lösung ist, die Punkte 1, 3 und 4 zu nehmen.