Ich habe Fragen, die das Folgende:Ranzen Algorithmus mit zwei Gewichten
Lösen Sie den Ranzen 0-1 Problem (nicht fraktionierten) Unter der Annahme, dass jedes bezwecken Gewicht
w1oderw2(es gibt nur zwei Gewichte). Kapazität = W, der Algorithmus muss auf O (nlogn) laufen.
Ich habe versucht zu lösen, der Greedy-Algorithmus funktioniert nicht, der dynamische Programmieralgorithmus ist O (n * W).
Kann mir jemand einen Hinweis geben. Danke.
Sie können die Elemente in zwei Teile unterteilen laufen, eine, die w1 wie Gewicht und die andere, die w2 haben als Gewicht.
Jetzt können Sie die beiden obigen Listen nach ihren Kosten sortieren.
A1: nach Kosten sortiert in absteigender Reihenfolge, Elemente, die Gewicht haben als w1
A2: sortiert nach Kosten in absteigender Reihenfolge, Elemente, die Gewicht haben als w2
Jetzt können Sie erstellen Präfix Summe von beiden das Array können sie P1, P2 anrufen.
Beispiel:
Array : 11, 8, 5, 3, 1
Prefix sum : 11, 19, 24, 27, 28
Sobald Sie die Präfixsumme haben, können Sie über die P1 Array durchlaufen und versuchen, Elemente bis zu der i-ten Index aufzunehmen. Sobald wir Elemente bis zu i enthalten, haben wir W - (w1*i) Gewicht übrig, dann können wir versuchen, dieses Gewicht im Array P2 binär zu suchen.
Pseudo-Code:
A : input array
create A1 : cost of elements having w1 weight
create A2 : cost of elements having w2 weight
sort(A1, descending)
sort(A2, descending)
for(i=0;i <= A1.size();i++){
P1[i] = P[i-1] + A1[i];
P2[i] = P[i-1] + A2[i];
}
int ans = 0;
for(i=1;i<=A1.size();i++){
if(i * w1 <= W){
int wLeft = W - i * w1;
int ans = binarySearch(wLeft, P2) + p1[i];
}
}
ans => contains the answer
//-----------Binary search function
int binarySearch(int weight, P2[]){
int start = 0, end = P2.size(), ans = 0;
int mid = (start+end)/2;
while(start <= end){
if(mid * w2 <= weight){
start = mid + 1;
ans = max(ans, p2[mid]);
}else{
end = mid - 1;
}
}
return ans
}
Die Gesamtkomplexität ist O(n * log n).
Wie von @j_random_hacker vorgeschlagen, können wir über das zweite Präfix-Array iterieren, da wir die Lösung nur durch Hinzufügen von Elementen verbessern können. Dies würde den Code vereinfachen, indem die binäre Suche entfernt wird.
Da es zwei Gewichte können Sie:
Erster Einsatz so viele Elemente w1 wie Sie haben, oder können in W. Nach ihnen so viele w2 wie möglich passen.
Wenn Sie solche Rucksack, in jeder Iteration bekommen Pop 1 w1 Element, und setzen Sie so viele w2 wie passen oder Sie haben. Sie tun dies, solange Sie w1 Elemente im Rucksack haben.
Höchstgewicht von Ranzen aus allen Iterationen werden Sie anwser und Algorithmus in O (n)
Dies scheint die einzige Lösung zu sein, die die Werte/Kosten berücksichtigt (aus Fairness hätte das OP klarer sein können, dass das Problem diese beinhaltet). Sie können die binäre Suche in der inneren Schleife durch einen Zeiger j ersetzen, der vom Ende von P2 rückwärts läuft, obwohl dies die Zeitkomplexität nicht verbessert, da die Sortierung immer noch dominiert. –