Anonymous user
Knapsack problem/Bounded: Difference between revisions
m
→{{header|Python}}
No edit summary |
|||
Line 3,243:
<lang python>from itertools import groupby
from collections import namedtuple
def anyvalidcomb(items, maxwt, val=0, wt=0):
' All combinations below the maxwt '
if not items:
Line 3,251 ⟶ 3,250:
else:
this, *items = items # car, cdr
for n in range(this.number + 1):
v = val + n * this.value
w = wt + n * this.weight
if w > maxwt:
break
for
yield [this] * n +
maxwt = 400
Line 3,288 ⟶ 3,287:
) ]
bagged = max( anyvalidcomb(items, maxwt), key=lambda c: (c[VAL], -c[WT])) # max val or min wt if values equal
print("Bagged the following %i items
print("for a total value of %i and a total weight of %i" % bagged[1:])</lang>
{{out}}
| |||