动态规划-背包问题

问题描述：0-1背包问题
输入：
一个背包，容量为 W。
n 个物品，每个物品有重量 w[i] 和价值 v[i]。
目标：在不超过背包容量的前提下，选择物品使得总价值最大。
限制：每个物品只能选 0 次（不选）或 1 次（选），不能分割。
示例：

背包容量 W = 5。
物品列表：[(重量, 价值)] = [(2, 3), (3, 4), (4, 5)]。
最大价值是多少？

动态规划的原理

1. 分解问题：定义状态
   动态规划将问题分解为子问题，并通过状态表示子问题的解。对于背包问题：

状态定义：dp[i][j] 表示前 i 个物品在背包容量为 j 时的最大价值。
i：物品的索引（从 0 到 n-1）。
j：背包的剩余容量（从 0 到 W）。
2. 状态转移方程
对于每个物品 i 和容量 j，有两种选择：

不选第 i 个物品：dp[i][j] = dp[i-1][j]（价值不变）。
选第 i 个物品：如果 w[i] <= j，则 dp[i][j] = dp[i-1][j - w[i]] + v[i]（价值增加 v[i]，但容量减少 w[i]）。
最终取两种选择的最大值：

python
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]) # 如果 w[i] <= j
3. 初始化
当 i = 0（没有物品）或 j = 0（容量为 0）时，dp[0][j] = 0 和 dp[i][0] = 0（无法装任何物品，价值为 0）。
4. 计算顺序
外层循环：遍历物品 i（从 1 到 n）。
内层循环：遍历容量 j（从 1 到 W）。
按顺序填充 dp 表，确保计算 dp[i][j] 时，dp[i-1][…] 已经计算完成。
5. 返回结果
最终结果是 dp[n][W]，即前 n 个物品在容量为 W 时的最大价值。

#include<iostream>#include<vector>#include<algorithm>// 用于 std::maxusingnamespacestd;intknapsack_01(intW,vector<pair<int,int>>&items){intn=items.size();// 物品数量// dp[i][j] 表示前 i 个物品在容量 j 时的最大价值vector<vector<int>>dp(n+1,vector<int>(W+1,0));for(inti=1;i<=n;++i){intw=items[i-1].first;// 当前物品的重量intv=items[i-1].second;// 当前物品的价值for(intj=1;j<=W;++j){if(w>j){// 当前物品太重，无法装入背包dp[i][j]=dp[i-1][j];}else{// 选择装或不装当前物品，取最大值dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v);}}}returndp[n][W];// 返回最大价值}intmain(){intW=5;// 背包容量vector<pair<int,int>>items={{2,3},{3,4},{4,5}};// (重量, 价值)intmax_value=knapsack_01(W,items);cout<<"最大价值: "<<max_value<<endl;// 输出: 7return0;}

代码解析
输入参数：
W：背包的最大容量。
items：物品列表，每个物品是一个 pair<int, int>，分别表示重量和价值。
动态规划表 dp：
dp[i][j] 表示前 i 个物品在背包容量为 j 时的最大价值。
初始化时，dp 表的所有值设为 0。
状态转移：
不选第 i 个物品：dp[i][j] = dp[i-1][j]（直接继承前 i-1 个物品的结果）。
选第 i 个物品：如果 w <= j，则 dp[i][j] = dp[i-1][j - w] + v（装入当前物品，价值增加 v，但容量减少 w）。
最终取两者的最大值：
cpp
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w] + v);
初始化：
dp[0][j] = 0（没有物品时价值为 0）。
dp[i][0] = 0（容量为 0 时无法装任何物品）。
结果：
dp[n][W] 即为前 n 个物品在容量 W 时的最大价值。