1. 问题

[背包问题：
、非形式化描述：
一个旅行者准备随身携带一个背包。
可以放入背包的物品有 n 种，物品 j 的 重量 和 价值 分别为 wj，vj，j=1,2….,n
如果背包的最大重量限制是 b，怎么选择放入背包物品以使得背包的价
值最大。

2. 解析

3. 设计

void findMax() { //动态规划
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= bagV; j++) {
if (j < w[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
}

void findWhat(int i, int j) { //最优解情况
if (i >= 0) {
if (dp[i][j] == dp[i - 1][j]) {
item[i] = 0;
findWhat(i - 1, j);
}
else if (j - w[i] >= 0 && dp[i][j] == dp[i - 1][j - w[i]] + v[i]) {
item[i] = 1;
findWhat(i - 1, j - w[i]);
}
}
}

4. 分析

时间复杂度以及空间复杂度均为ｏ（Ｎ×Ｖ）

5. 源码

https://github.com/joserfdave/arithmetic/tree/main