Knapsack(dynamic programming)
Δημοσιεύτηκε: Παρ Μάιος 08, 2009 8:00 pm
Αυτος εδω ο κωδικας ειναι για το Knapsack problem σε Pascal(Απο το Βιβλιο algorithms) :
for j:=1 to N do begin // j is the item number
for i:=1 to M do // i is the size of knapsack
if (i-size[j]>=0) then
if cost<(cost[i-size[j]]+val[j]) then
begin
cost:=cost[i-size[j]]+val[j];
best:=j;
end;
end;
Χρειαζομαι να το κανω να λειτουργισει για ενα περιορισμενο αριθμο αντικειμενων αλλα ακομα να το υλοποιησω.Σκεφτομαι να κανς τον πινακα cost δυσδιαστατο αλλα χρειαζομαι και την δικη σας γνωμη.
for j:=1 to N do begin // j is the item number
for i:=1 to M do // i is the size of knapsack
if (i-size[j]>=0) then
if cost<(cost[i-size[j]]+val[j]) then
begin
cost:=cost[i-size[j]]+val[j];
best:=j;
end;
end;
Χρειαζομαι να το κανω να λειτουργισει για ενα περιορισμενο αριθμο αντικειμενων αλλα ακομα να το υλοποιησω.Σκεφτομαι να κανς τον πινακα cost δυσδιαστατο αλλα χρειαζομαι και την δικη σας γνωμη.