Интересная задачка :)
Здравствуйте. Столкнулся с проблемой и котелок не может придумать решение. Хочу подключить коллективный мозг. Для упрощения понимания придумаю гипотетический пример. Суть следующая:
Предположим, у нас есть некий магазин в котором нужно купить определённый товар, который стоит (X) долларов. Х - это переменная и каждый раз её значение меняется. Ну для примера возьмём за X сумму в $117.47. Но самих денег у нас нет, а оплачиваем мы акциями(или, если хотите, марками, или фантиками). Суть в том, что акции/марки/фантики стоят тоже по-разному. Допустим, акции у нас разных фирм и каждая акция стоит по-своему. Цена может колебаться от $0.5 до $200 за штуку. И задача состоит в том, чтобы набрать акций на сумму ровно $117.47, если это возможно, а если невозможно, то на максимально близкую сумму к нашему (X), но не меньше. Т.е. можно набрать акций на $117.47, на $117.48, $117.49, $117.50. Если разница больше, чем в 4 цента, то это уже критично. Для примера вот массив с ценами наших акций: [0.67, 0.84, 0.86, 0.86, 0.89, 1.7, 1.8, 1.87, 1.99, 2, 2.01, 2.06, 2.09, 2.85, 2.88, 2.99, 3.14, 3.17, 4.45, 4.49, 5.01, 5.76, 5.78, 8.91, 9, 12.54, 17.83, 54.11, 77.12, 103.3, 140.88] У меня в голову только дуратские варианты лезут. Может у кого-нибудь есть более-менее деликатные варианты. Важно чтобы это было не очень ресурсозатратно и времязатратно, в случае если массив цен акций содержит большое количество элементов. Обычно это не больше 300 элементов. |
1п. берем последнюю ячейку массива, если она больше стоимости меняем ее на предпоследнюю и так далее.. пока не дойдем до меньшей или до наиболее минимально возможной.
2п. если последняя ячейка не больше стоимоти, то сохраняем ее в переменную и к ней будем плюсовать следующую по тому же алгоритму что и первом пункте. |
чтобы максимально точно попасть в стоимость нужно будет использовать какой то более сложный алгоритм. это уже вопрос больше к математикам.
|
Цитата:
|
Цитата:
|
-FIXER-,
так? alert(2*54.11 +0.84 * 10 + 1 * 0.86) |
Цитата:
|
:write: :)
alert(2.06 * 49 + 5.76 * 2 + 5.01)//117.47 |
Цитата:
|
Цитата:
|
|
Цитата:
причем, тут "ранцем" будет разница между ценой предмета и суммарной стоимостью всех имеющихся акций, а "весом" и "ценностью" каждой акции - её стоимость. Тогда решение - набор тех акций, которые не используем при покупке. если каждой акции по одной штуке, то это "Рюкзак 0-1", и можно сказать, повезло :) |
nerv_,
Alexandroppolus, ничего не понимаю, ни википедию, ни вас, а код существует для такого? P.S. пробовал написать полный перебор, комп не справляется, видимо не слишком оптимально или где ошибка. |
Цитата:
"Рюкзак 0-1" разруливается за полиномиальное время (на подобных объемах отработает мгновенно). Код надо поискать, должен быть ) |
Alexandroppolus,
спасибо, ещё бы понять что такое Цитата:
|
nerv_,
спасибо, но я не понимаю что там написано, особенно математические формулы. Цитата:
|
рони,
Цитата:
Цитата:
Что я сделал: 1. взял N-первых весов из первого поста 2. домножил их на 100, чтобы получить целые числа 3. задал цель равную 247 4. взял алгоритм из википедии для рюкзака 0-1 результат см. ниже const costs = [67, 84, 86, 86, 89, 170, 180, 187, 199, 200, 201, 206, 209] const capacity = 247 /** * @see [url]https://ru.wikipedia.org/wiki/Задача_о_ранце[/url] * @param {Array.<Number>} v Ценности предметов (загруженные в массив v) * @param {Array.<Number>} w Веса предметов (загруженные в массив w) * @param {Number} n Количество предметов (n) * @param {Number} W Грузоподъемность (W) * @return {Array.<Number>} */ function solveKnapsack01(v, w, n, W) { let m = new Array(n) for (let i = 0; i <= n; i++) { m[i] = new Array(W + 1).fill(0) } for (let i = 1; i < n; i++) { for (let j = 0; j <= W; j++) { if (w[i] > j) { m[i][j] = m[i - 1][j] } else { m[i][j] = Math.max(m[i - 1][j], m[i - 1][j - w[i]] + v[i]) } } } return m } console.log(solveKnapsack01(costs, costs, costs.length, capacity)) Но это еще не все решение: Цитата:
--- Также обращаю внимание на пост Alexandroppolus: Цитата:
|
nerv_,
спасибо за попытку, но бесполезно - не понимаю как строится дерево, не понимаю что за результат в строке 33, и уж тем более почему надо искать набор акций которые не используем при покупке. то что такой вариант называется Рюкзак 0-1, пусть, но мне это ни очём не говорит. как там говорится: нельзя обьять необьятное, но зато мы поём и пляшем. |
Цитата:
|
:no: Конечно алгоритм нужен
|
Часовой пояс GMT +3, время: 23:59. |