Уведомления

Группа в Telegram: @pythonsu

#1 Июль 16, 2013 11:43:12

Ad_pro
Зарегистрирован: 2013-07-16
Сообщения: 2
Репутация: +  0  -
Профиль   Отправить e-mail  

Перебор 2^1000 комбинаций

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

Т.е. например рюкзак может взять 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)])

Офлайн

#2 Июль 16, 2013 13:15:31

4kpt
От: Харьков
Зарегистрирован: 2010-11-03
Сообщения: 998
Репутация: +  63  -
Профиль   Отправить e-mail  

Перебор 2^1000 комбинаций

Ad_pro
Вы вообще слышали про оптимизацию?
Почитайте любую литературу. Рекомендую Банди Б. “Методы оптимизации. Вводный курс”. Для новичка - самое оно.

P.S. Решать задачу оптимизации перебором это адский хардкор :)



Офлайн

#3 Июль 16, 2013 18:35:53

doza_and
От:
Зарегистрирован: 2010-08-15
Сообщения: 4138
Репутация: +  252  -
Профиль   Отправить e-mail  

Перебор 2^1000 комбинаций

Ad_pro
Возможно, у вас есть какое-то другое видение

Из описания задачи неясно почему вы не можете сделать:

Картошка_1 10кг стоимостью 100р
Картошка_2 20кг стоимость 300р
….

и применить обычный алгоритм заполнения рюкзака.



Офлайн

#4 Июль 17, 2013 10:32:43

Ad_pro
Зарегистрирован: 2013-07-16
Сообщения: 2
Репутация: +  0  -
Профиль   Отправить e-mail  

Перебор 2^1000 комбинаций

doza_and
В условиях задачи имеется такое ограничение, что все предметы должны быть уникальными, т.е. нельзя взять сразу оба мешка картошки разного объёма\ценности, можно только один из них.

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version