Сильно усложненная задача о рюкзаке, хелп. - Программирование

sflash · 20.05.2005, 08:27

Нужно решение данной задачи в другой формулировке.
В задаче о рюкзаке просто массив чисел (весов предметов), которые надо уложить в рюкзак. А мне надо по другому.
Есть куча товаров (>10000), каждого товара определенное количество, у каждого товара есть сумма. нужно решение, сколько какого товара положить в корзину чтоб общая сумма была равна заданной. Я прикинул что если делать полным перебором, то к пенсии обсчитает. Подскажите алгоритм.

Drakosha · 20.05.2005, 11:10

насколько я помню, решается линейным программированием (simplex).
Не бейте если ошибаюсь...

trimel · 20.05.2005, 11:18

sflash, я не понял , тебе надо все возможные варианты товаров на заданную сумму , или определенных ? или что ?

20.05.2005, 11:19

Опять же прошу сильно не бить, но, как мне кажется, может стоит посмотреть в сторону генетических алгоритмов? Вот, например.

sflash · 20.05.2005, 11:23

Сделал пока перебором, максимальное время нахождения ~5 секунд, минимально - практически сразу, все зависит от исходной суммы и наличия товара. (комп P3-750). Компутер где будет веститсь расчет P4-2.8. Так что особо не заморачиваюсь, расчет нужен раз в месяц. Так что 5-10 максимум секунд в месяц можно и подождать. Если кому надо, исходник скину. А если кто предложит более нормальный подход то милости прошу.

Цитата:

Сообщение от trimel

sflash, я не понял , тебе надо все возможные варианты товаров на заданную сумму , или определенных ? или что ?

Нет, просто сколько каких на некоторую сумму. Один раз, а не все возможные комбинации.

Marat · 31.05.2005, 15:14

А я так понимаю, что обычное решение задачи о рюкзаке - т.е. методом динамического программирования - это и есть полный перебор, только оформленный немного иначе )) может и ошибаюсь, но приходилось им часто пользоваться...

04.06.2005, 13:18

эта задача является NP, на сколько я понял, так что или генетические или приближенные алгоритмы имхо. (генетические будут на порядок качественнее в зависимости от времени бежания программы, так что лучше имо их использовать)

20.05.2005, 08:27	# 1
sflash Junior Member Регистрация: 25.09.2003 Сообщения: 53	Сильно усложненная задача о рюкзаке, хелп. Нужно решение данной задачи в другой формулировке. В задаче о рюкзаке просто массив чисел (весов предметов), которые надо уложить в рюкзак. А мне надо по другому. Есть куча товаров (>10000), каждого товара определенное количество, у каждого товара есть сумма. нужно решение, сколько какого товара положить в корзину чтоб общая сумма была равна заданной. Я прикинул что если делать полным перебором, то к пенсии обсчитает. Подскажите алгоритм.

20.05.2005, 11:18	# 3
trimel Full Member Регистрация: 30.08.2004 Адрес: Новосибирск Сообщения: 3 146	sflash, я не понял , тебе надо все возможные варианты товаров на заданную сумму , или определенных ? или что ? __________________ Если эта надпись уменьшается - ваш монитор уносят.

31.05.2005, 15:14	# 6
Marat Newbie Регистрация: 23.11.2001 Адрес: Kazan Сообщения: 28	А я так понимаю, что обычное решение задачи о рюкзаке - т.е. методом динамического программирования - это и есть полный перебор, только оформленный немного иначе )) может и ошибаюсь, но приходилось им часто пользоваться... Последний раз редактировалось Marat; 31.05.2005 в 15:17.

20.05.2005, 11:10	# 2
Drakosha Full Member Регистрация: 16.10.2002 Адрес: ArchLinux, Internet Сообщения: 557	насколько я помню, решается линейным программированием (simplex). Не бейте если ошибаюсь...

20.05.2005, 11:19	# 4
IlyaPHP Guest Сообщения: n/a	Опять же прошу сильно не бить, но, как мне кажется, может стоит посмотреть в сторону генетических алгоритмов? Вот, например.

04.06.2005, 13:18	# 7
shalomman Guest Сообщения: n/a	эта задача является NP, на сколько я понял, так что или генетические или приближенные алгоритмы имхо. (генетические будут на порядок качественнее в зависимости от времени бежания программы, так что лучше имо их использовать)