Всем привет! Столкнулся с задачей из раздела оптимизации и комбинаторики, а именно- задача рюкзака. Суть в следующем - имеется набор предметов, ограничение по весу, вес и ценность каждого предмета. Но в отличие от классической задачи рюкзака, у каждого предмета есть два варианта цены и веса.

Т.е. например рюкзак может взять 20кг У нас есть Картошка 10кг стоимостью 100р Картошка 20кг стоимость 300р Бутылка пива 1кг стоимость 500р Бутылка пива 1кг стоимостью 100р и т.д. Т.е. для каждого предмета два варианта

Собственно как сейчас решаю задачу - из двух массивов входных данных получаю уникальные комбинации предметов (2^n комбинаций), загоняю каждую комбинацию в алгоритм рюкзака (использую “жадный алгоритм”), получаю массив выходных данных, беру решение с наибольшой “ценностью” - это и есть оптимальный вариант. Все работает нормально, если у нас не больше 10-15 предметов. Но если предметов становится 20,50,100,1000 - это 2^1000 комбинаций, и всё уходит в глубокую кому. Не получается даже завершить генерацию уникальных комбинаций.

Подскажите пожалуйста, как решиь данную проблему? Возможно, у вас есть какое-то другое видение на решение данной задачи?

Уникальные комбинации генерирую так:

E=[]
off = [1 2 3 4 5]
on = [a b c d e]
for choices in itertools.product([0, 1], repeat=len(off)):
 E.append([(on[j] if choice else off[j]) for j, choice in enumerate(choices)])