32 lines
644 B
Plaintext
32 lines
644 B
Plaintext
names$[] = [ "panacea" "ichor" "gold" ]
|
|
vals[] = [ 3000 1800 2500 ]
|
|
wgts[] = [ 0.3 0.2 2.0 ]
|
|
vols[] = [ 0.025 0.015 0.002 ]
|
|
maxwgt = 25
|
|
maxvol = 0.25
|
|
#
|
|
n = len names$[]
|
|
len cnt[] n
|
|
global best[] bestval .
|
|
#
|
|
proc knapsack i val wgt vol .
|
|
if i > n
|
|
if val > bestval
|
|
bestval = val
|
|
best[] = cnt[]
|
|
.
|
|
return
|
|
.
|
|
cnt[i] = lower floor (wgt / wgts[i]) floor (vol / vols[i])
|
|
while cnt[i] >= 0
|
|
knapsack i + 1 val + cnt[i] * vals[i] wgt - cnt[i] * wgts[i] vol - cnt[i] * vols[i]
|
|
cnt[i] -= 1
|
|
.
|
|
.
|
|
knapsack 1 0 maxwgt maxvol
|
|
for i to n
|
|
if best[i] > 0
|
|
print best[i] & " " & names$[i]
|
|
.
|
|
.
|