рони,
Цитата:
Сообщение от рони
например тут написано в единственнном почему???
|
потому, что существует ряд формулировок (вариантов) задач о рюкзаке. Формулировка, готорая гласит
Цитата:
не более одного экземпляра каждого предмета
|
носит название Рюкзак 0-1
Что я сделал:
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:
Цитата:
Сообщение от Alexandroppolus
причем, тут "ранцем" будет разница между ценой предмета и суммарной стоимостью всех имеющихся акций, а "весом" и "ценностью" каждой акции - её стоимость. Тогда решение - набор тех акций, которые не используем при покупке.
|
Понятно почему? :)
|
