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

[sflash]

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

[Drakosha]

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

[trimel]

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

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

[sflash]

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

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

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

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

[Marat]

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

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