希望藉由程式解題的過程重新打好程式基礎和學習遺漏的相關知識點
會將解題過程遇到困難的地方做個紀錄
測驗網站：LidemyOJ ( LIOJ ) by 胡立 ( Huli )
免費課程 — [ALG101] 先別急著寫 leetcode by 胡立 ( Huli )
討論區：Lidemy Discussions by 胡立 ( Huli )
這題 Level ( Medium ) 有提示可以搜尋 "背包問題"
🔖 文章索引
1. 參考文章
2. 推論公式
3. 程式碼
4. 延伸閱讀參考文章
https://segmentfault.com/a/1190000012829866
推論公式
假設背包最大可負重: 10，總品項: 5
品項 ( 重量, 價值 )
品項一 ( 2, 6 )
品項二 ( 2, 3 )
品項三 ( 6, 5 )
品項四 ( 5, 4 )
品項五 ( 4, 6 )
根據下圖第二行 紅字 6，這邊需要去比較 i = 1, j = 2 和 i = 2, j = 2 時哪一個價值比較大，從表看出 i = 1, v = 6、i = 2, v = 3 可推論出價值 6 比較大。
根據下圖第二行 紅字 9，因背包重量 ( j ) = 4，i = 1 和 i = 2 的 w 都是 2 所以都能裝進去背包，價值由 i = 1, v = 6，i = 2, v = 3 得出 6 + 3 = 9。
根據下圖第三行 紅字 6，當 i = 3, j = 2, w = 6 這邊可得知背包重量 ( j ) < 物品重量 ( w ) 的最大價值會是 ( i — 1, j ) 的價值
根據下圖第三行 紅字 9，當背包重量 ( j ) 等於物品重量 ( w ) 時會需要去比較當前物品價值與 ( i — 1, j ) 的價值哪一個大
根據下圖第三行 紅字 11，當背包重量 ( j ) 大於物品重量 ( w ) 時會得出公式 max ( ( i-1, j ), ( i-1, j — Wi ) + Vi )
根據公式
- ( i — 1, j ) Condition ( j < Wi && i > 0 )
- max ( ( i-1, j ), ( i-1, j — Wi ) + Vi ) Condition ( j ≥ Wi && i > 0 )
會多增加物品重量 0、物品價值 0 這一行
因為物品一套入公式 ( i — 1, j ) 時需要
程式碼
會發現 log(DP) 出來看結果時會跟上圖的表一模一樣
# input
5 10
2 6
2 3
6 5
5 4
4 6var readline = require('readline');
var lines = []
var rl = readline.createInterface({
input: process.stdin
});
rl.on('line', function (line) {
lines.push(line)
});
rl.on('close', function() {
solve(lines)
})
const log = console.log;
function solve(lines) {
const [AMOUNT, BAG_WEIGHT] = lines[0].split(' ').map(Number);
const WEIGHTS = [];
const VALUES = [];
for (let i = 1; i <= AMOUNT; i++) {
let [weight, value] = lines[i].split(' ').map(Number);
WEIGHTS.push(weight);
VALUES.push(value);
}
knapsack(BAG_WEIGHT, WEIGHTS, VALUES, AMOUNT);
}
function knapsack(bag_weight, weights, values, amount) {
let DP = [];
for (let i = 0; i <= amount; i++) {
DP[i] = [];
for (let j = 0; j <= bag_weight; j++) {
if (i === 0 || j === 0) {
DP[i][j] = 0;
continue;
}
if (j < weights[i - 1]) {
DP[i][j] = DP[i - 1][j];
}
if (j >= weights[i - 1]) {
DP[i][j] = Math.max(DP[i - 1][j], DP[i - 1][j - weights[i - 1]] + values[i-1]);
}
}
}
log(DP[amount][bag_weight]);
}
