2023年8月1日发(作者：)

关于动态规划01背包问题的⼀些⼼得体会《算法笔记》动态规划之01背包问题状态转移⽅程的代码为：for(int i = 1; i <= n; i++){ //n件物品 for(int j = w[i]; j <= c; j++){ //每件物品的重量为w[i]，

价值为v[i],

背包最⼤容量为c dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]; }}

搜索CSDN⼤佬博客得出的代码为：for(int i = 1; i <= n; i++){ for(int j = 1; j <= c; j++){ if(j < w[i]){ //如果当前背包容量不⾜以装下第i件物品 dp[i][j] = dp[i-1][j]; //只能选择不装 }else{ //如果当前背包容量⾜以装下第i件物品 //但由于装第i件物品不⼀定使得价值最⼤，所以考虑装与不装第i件物品所能得到的最⼤价值 dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]); } } }个⼈更倾向于第⼆种代码，对于第⼀种代码的正确性存在疑问。原因是第⼀种代码的内层循环，j从w[i]开始取值，这样在填表dp[i][j]的时候会漏填部分表格导致中间部分dp[i][j]的结果错误。举个例⼦，假设现在有6件商品，背包容量最⼤为12商品的重量为：w[i] = {4, 6, 2, 2, 5, 1}商品的价值为：v[i] = {8, 10, 6, 3, 7, 2}分别⽤两种代码填写dp数组，打印两个表格。#include #include #include using namespace std;const int maxn = 100;int main(){ int v[maxn], w[maxn], dp[maxn][maxn] = {0}; int n, c; cin >> n >> c; for(int i = 1; i <= n; i++){ //输⼊价值数组 cin >> v[i]; } for(int i = 1; i <= n; i++){ //输⼊重量数组 cin >> w[i]; } for(int i = 1; i <=n; i++){ //第⼀种代码 for(int j = w[i]; j <= c; j++){ dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]); } } for(int i = 1; i <= n; i++){ //打印dp数组 for(int j = 1; j <= c; j++){ cout << dp[i][j]; if(j < c) cout << "t"; else cout << endl; } } return 0;}#include #include #include using namespace std;const int maxn = 100;int main(){ int v[maxn], w[maxn], dp[maxn][maxn] = {0}; int n, c; cin >> n >> c; for(int i = 1; i <= n; i++){ //输⼊价值数组 cin >> v[i]; } for(int i = 1; i <= n; i++){ //输⼊重量数组 cin >> w[i]; } for(int i = 1; i <= n; i++){ //第⼆种代码 for(int j = 1; j <= c; 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]); } } } for(int i = 1; i <= n; i++){ //打印dp数组 for(int j = 1; j <= c; j++){ cout << dp[i][j]; if(j < c) cout << "t"; else cout << endl; } } return 0;}两种⽅法打印出来的数组分别如下：第⼀种：第⼆种：可以看到，虽然两种⽅法最优解都是24，但中间部分dp[i][j]有了很⼤的出⼊。第⼆种的dp数组才是正确的。

2023年8月1日发(作者：)

关于动态规划01背包问题的⼀些⼼得体会《算法笔记》动态规划之01背包问题状态转移⽅程的代码为：for(int i = 1; i <= n; i++){ //n件物品 for(int j = w[i]; j <= c; j++){ //每件物品的重量为w[i]，

价值为v[i],

背包最⼤容量为c dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]; }}

搜索CSDN⼤佬博客得出的代码为：for(int i = 1; i <= n; i++){ for(int j = 1; j <= c; j++){ if(j < w[i]){ //如果当前背包容量不⾜以装下第i件物品 dp[i][j] = dp[i-1][j]; //只能选择不装 }else{ //如果当前背包容量⾜以装下第i件物品 //但由于装第i件物品不⼀定使得价值最⼤，所以考虑装与不装第i件物品所能得到的最⼤价值 dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]); } } }个⼈更倾向于第⼆种代码，对于第⼀种代码的正确性存在疑问。原因是第⼀种代码的内层循环，j从w[i]开始取值，这样在填表dp[i][j]的时候会漏填部分表格导致中间部分dp[i][j]的结果错误。举个例⼦，假设现在有6件商品，背包容量最⼤为12商品的重量为：w[i] = {4, 6, 2, 2, 5, 1}商品的价值为：v[i] = {8, 10, 6, 3, 7, 2}分别⽤两种代码填写dp数组，打印两个表格。#include #include #include using namespace std;const int maxn = 100;int main(){ int v[maxn], w[maxn], dp[maxn][maxn] = {0}; int n, c; cin >> n >> c; for(int i = 1; i <= n; i++){ //输⼊价值数组 cin >> v[i]; } for(int i = 1; i <= n; i++){ //输⼊重量数组 cin >> w[i]; } for(int i = 1; i <=n; i++){ //第⼀种代码 for(int j = w[i]; j <= c; j++){ dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]); } } for(int i = 1; i <= n; i++){ //打印dp数组 for(int j = 1; j <= c; j++){ cout << dp[i][j]; if(j < c) cout << "t"; else cout << endl; } } return 0;}#include #include #include using namespace std;const int maxn = 100;int main(){ int v[maxn], w[maxn], dp[maxn][maxn] = {0}; int n, c; cin >> n >> c; for(int i = 1; i <= n; i++){ //输⼊价值数组 cin >> v[i]; } for(int i = 1; i <= n; i++){ //输⼊重量数组 cin >> w[i]; } for(int i = 1; i <= n; i++){ //第⼆种代码 for(int j = 1; j <= c; 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]); } } } for(int i = 1; i <= n; i++){ //打印dp数组 for(int j = 1; j <= c; j++){ cout << dp[i][j]; if(j < c) cout << "t"; else cout << endl; } } return 0;}两种⽅法打印出来的数组分别如下：第⼀种：第⼆种：可以看到，虽然两种⽅法最优解都是24，但中间部分dp[i][j]有了很⼤的出⼊。第⼆种的dp数组才是正确的。