У меня есть понимание основной проблемы с рюкзаком 0-1 и ее решения. Я пытаюсь решить вариант проблемы 0-1, когда вместо того, чтобы выбирать любую комбинацию элементов из одного списка, вы должны выбрать ровно один элемент из множества наборов различных элементов. .
Например, в моей задаче список элементов будет выглядеть так:
Еда
- Банан (вес 9, ценность 10)
- Хлеб (вес 3, ценность 25)
- Яблоко (вес 4, ценность 30)
- ...
Рубашки
- Футболка (вес 2, ценность 20)
- Рубашка на пуговицах (вес 3, ценность 25)
- ...
Брюки
- Хаки (вес 4, ценность 30)
- Джинсы (вес 2, ценность 30)
- ...
и так далее, где задача требует, чтобы вы выбрали ровно один предмет из еды, один предмет из рубашек, один предмет из брюк и так далее.
Я думаю, что у меня есть решение для грубой силы, которое я модифицировал из Rosetta Code и, похоже, оно работает (ниже), но мне трудно понять, как создать более эффективное решение для динамического программирования. Может ли кто-нибудь помочь или указать мне в правильном направлении? Я бы оценил это.
from itertools import product
def anycomb(item1, item2, item3, item4):
return ( comb
for comb in product(item1, item2, item3, item4)
)
def totalvalue(comb):
' Totalise a particular combination of items'
totwt = totval = 0
for item, wt, val in comb:
totwt += wt
totval += val
return (totval, -totwt) if totwt <= 400 else (0, 0)
itemset_1 = (
("map", 9, 150), ("compass", 13, 35), ("water", 153, 200), ("sandwich", 50, 160),
("glucose", 15, 60))
itemset_2 = (
("tin", 68, 45), ("banana", 27, 60), ("apple", 39, 40),
("cheese", 23, 30), ("suntan cream", 11, 70))
itemset_3 = (
("beer", 52, 10), ("camera", 32, 30),
("t-shirt", 24, 15), ("trousers", 48, 10), ("umbrella", 73, 40),
("waterproof trousers", 42, 70))
itemset_4 = (
("waterproof overclothes", 43, 75),
("note-case", 22, 80), ("sunglasses", 7, 20), ("towel", 18, 12),
("socks", 4, 50), ("book", 30, 10))
bagged = max( anycomb(itemset_1, itemset_2, itemset_3, itemset_4), key=totalvalue) # max val or min wt if values equal
print("Bagged the following items\n " +
'\n '.join(sorted(item for item,_,_ in bagged)))
val, wt = totalvalue(bagged)
print("for a total value of %i and a total weight of %i" % (val, -wt))
