День добрый, уважаемые)
Столкнулся с такой задачей:
Например, у нас есть 4 предмета(может быть сколько угодно) и их цена
1 - 5p
2 - 10p
3 - 5p
4 - 10p
Задача стоит такая, выбрать отсюда предметы таким образом, чтобы они удовлетворяли условию: сумма выбранных предметов = 30%(+-5% (например) от общей суммы предметов.
В данном случае возможны такие комбинации: 1,3 и 2. ( В приоритете комбинация с меньшим кол-ов предметов)
Т.е нужно получить максимально близкую к N% от общей суммы комбинацию предметов.
Кто нибудь сталкивался с подобными алгоритмами?
Есть примеры решения/алгоритмов?
Предполагаю, что сначала нужно построить все сочетания без повторений, и из них уже выбрать наиболее подходящее сочетание?
uvelichitel, bobrovskyserg:
полагаю, в моем случае вес будет совпадать со стоимостью?
это получается уже подвид задачи о рюкзаке - задача о суммах подмножеств?
Попробовал и тот и тот алгоритм, реализованный на php
До 20 предметов считает быстро, на 40 уже очень медленно (10-12секунд), на 50 предметах виснет. В моем случае чаще всего будет около 100 предметов :(
br1an:
"тот и тот алгоритм" - какие именно?
Обратите внимание, что задача идёт туго при произвольных ценах, тогда как разные спец. случаи решаются легко.
Например, набор цен 1, 2, 4, 8 ... даёт однозначное решение для любой суммы (в задаче без ограничения на число товаров).
uvelichitel:
Задача рюкзака здесь очевидно подменена задачей представления произвольного целого числа в двоичной системе, всегда имеющей единственное решение.
bobrovskyserg, uvelichitel: 1 - Задача о рюкзаке (Метод динамического программирования), реализовано тут coma-coding.com/blog/javascript-knapsack-solver
Я переписал под себя, считает быстро и вроде бы правильно. НО не учел, что в данной задачи (о рюкзаке) должны использоваться целочисленные значения веса и цены, а у меня такое редко встречается, как итог, алгоритм находит не самое оптимальное решение. Есть ли разновидность этой задачи/других с учетом дробных значений?
2 - Задача о сумме подмножеств, алгоритмы которые я нашел, считают перебором, в итоге на 40-50 просто повисают
br1an:
В килограмме 1000 грамм, в рубле 100 копеек - зачем тут дроби?
Просто массив, на котором ты будешь работать ДП-алгоритмом, станет кратно длиннее, а скорость кратно понизится. Если это нежелательно - отбрось копейки, а потом пересчитывай точную сумму для приближенных решений на отрезке целевая_сумма-число_предметов ... целевая_сумма (опять перебор, хехе).
Простой
