算法|DP 背包问题
DP 背包问题
分类
重点关注 01背包和完全背包即可
- 01 背包: 只有一个, 选或者不选
- 完全被包:无限个数, 选还是不选
背包逻辑
function testWeightBagProblem(weight, value, size) {
const len = weight.length;
const dp = Array(len)
.fill()
.map(() => Array(size + 1).fill(0));
// 初始化 第一个物品的重量, 无论几个总重量是多少,都等于第一个起始重量
for (j = weight[0]; j <= size; j++) {
dp[0][j] = value[0];
}
// 循环物品
for (let i = 1; i < len; i++) {
// 循环背包
for (let j = 0; j <= size; j++) {
// 当前重量大于背包重量
if (weight[i] > j) {
dp[i][j] = dp[i - 1][j];
} else {
// dp[i - 1][j - weight[i]] 为j - weight[i] 不放物品时候的最大价值
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
console.table(dp);
}
return dp[len - 1][size];
}
console.log(testWeightBagProblem([2, 3, 5], [15, 20, 30], 6));
┌─────────┬───┬───┬────┬────┬────┬────┬────┐
│ (index) │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │
├─────────┼───┼───┼────┼────┼────┼────┼────┤
│ 0 │ 0 │ 0 │ 15 │ 15 │ 15 │ 15 │ 15 │
│ 1 │ 0 │ 0 │ 15 │ 20 │ 20 │ 35 │ 35 │
│ 2 │ 0 │ 0 │ 15 │ 20 │ 20 │ 35 │ 35 │
└─────────┴───┴───┴────┴────┴────┴────┴────┘
35
记录点
- 定义dp, 到底是一维还是二维数组,默认是填0,不可直接fill([0,0]), 会内存地址公用
- 初始化dp数组, 来一个for循环,这里的起点是物品重量的起始值
- 双for循环, 从物品循环, 再重量循环
- 当前物品重量大于 j, 则沿用上一个dp值, 反之取上一个dp值和 不放该物品的dp值+该物品的价值中的最大值
- 返回结果
- 递推公式 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) 还是挺绕的, 需要记忆
- 凡是有i-1的循环, 必须考虑多生成一个长度, 从0开始, 如size本来是6, 生成的二维数组要size+1, 变成7个
原文地址:https://blog.csdn.net/shjavadown/article/details/136234544
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!