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，要当作成员变量的话，如果你没初始化，那你的数组就是一串乱值。

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

原文地址：https://blog.csdn.net/Ricky_youngone/article/details/142393033

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！