1267：【例9.11】01背包问题（信奥一本通）

题目链接：信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

今天刚看完卡尔大哥讲解的01背包，今天手敲了一遍，还是很多问题，只能说自己还是刷题太少或者说是没理解到位。

代码如下

# include <iostream>
# include <cstring>
using namespace std;
int dp[1010][1010]; //1.dp[i][j] 表示着在有限的容量内使背包里面物品价值总和最大 
// 2.dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i])
int w[200], c[200];
int main()
{int m, n; //w[i]是重量, c[i]是物品的价值 cin>>m>>n;memset(dp, 0, sizeof(dp));for(int i = 1; i <= n; i++){cin>>w[i]>>c[i];}for(int j = w[0]; j <= m; j++)  //3.初始化行和列 {dp[0][j] = c[0];}for(int j = 1; j <= m; j++) //4.遍历顺序{for(int i = 1; i <= n; i++){if(w[i] > j){dp[i][j] = dp[i - 1][j];}else{dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i]);}}}//for(int i = 0; i <= n; i++) //打印二维dp数组//{//   for(int j = 0; j <= m; j++)//    {//        cout<<dp[i][j]<<" ";//    }//    cout<<endl;//}cout<<dp[n][m]<<endl;  //打印dp结果，如果错误的话，需要自己打印二维dp,如上return 0;
}

代码讲解：只讲核心。先确定dp[i][j]的含义，正如我解释所说的，dp[i][j]表示着在有限的容量内使背包里面物品价值总和最大。然后就根据这个含义定义好dp[i][j]的状态转移方程，dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i])，为什么是max而不是min，也很好理解，也就是我们需要求最大的价值，所以就要用max。其实是初始化，就是对于首行和首列初始化，为什么要初始化这两个，因为后面的dp是从上面dp[i - 1][j]和左上角dp[i - 1][j - x]来的，然后就是遍历顺序，这个遍历顺序一定要搞清楚顺序，为什么第一层是j而不是i，因为是先遍历背包，在遍历物品（当然，你先遍历物品，在遍历背包是一样的）所以dp[i][j]后面的[j]也就是背包（列），所以先遍历j，最后输出的是dp[n][m]，值得注意的是，我们最好把数组定义为局部变量，这样自动初始化为0，要当作成员变量的话，如果你没初始化，那你的数组就是一串乱值。

感悟：因为以前看过信奥这个团队讲解的这个题目，我今天又按照自己的思路编写了这个代码，实际上我还发现这个团队有一点没讲到位，就是初始化这一知识点，那个团队没有写这个初始化代码，虽说这个题目不需要这一段代码也能过，但是也是很必要写上的，毕竟对于我们这种开始学习动态规划的小白来说，最好是写上。