30 lines
1.0 KiB
Plaintext
30 lines
1.0 KiB
Plaintext
weights := [9,13,153,50,15,68,27,39,23,52,11,32,24,48,73,42,43,22,7,18,4,30]:
|
|
vals := [150,35,200,160,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10]:
|
|
items := ["map","compass","water","sandwich","glucose","tin","banana","apple","cheese","beer","suntan cream","camera","T-shirt","trousers","umbrella","waterproof trousers","waterproof overclothes","note-case","sunglasses","towel","socks","book"]:
|
|
acc := Array(1..numelems(vals)+1,1..400+1,1,fill=0):
|
|
len := numelems(weights):
|
|
for i from 2 to len+1 do #number of items picked + 1
|
|
for j from 2 to 401 do #weight capacity left + 1
|
|
if weights[i-1] > j-1 then
|
|
acc[i,j] := acc[i-1, j]:
|
|
else
|
|
acc[i,j] := max(acc[i-1,j], acc[i-1, j-weights[i-1]]+vals[i-1]):
|
|
end if:
|
|
end do:
|
|
end do:
|
|
printf("Total Value is %d\n", acc[len+1, 401]):
|
|
count := 0:
|
|
i := len+1:
|
|
j := 401:
|
|
while (i>1 and j>1) do
|
|
if acc[i,j] <> acc[i-1,j] then
|
|
printf("Item: %s\n", items[i-1]):
|
|
count := count+weights[i-1]:
|
|
j := j-weights[i-1]:
|
|
i := i-1:
|
|
else
|
|
i := i-1:
|
|
end if:
|
|
end do:
|
|
printf("Total Weight is %d\n", count):
|