Суть в следующем - имеется набор предметов, ограничение по весу, вес и ценность каждого предмета. Но в отличие от классической задачи рюкзака, у каждого предмета есть два варианта цены и веса.
Т.е. например рюкзак может взять 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)])