快递公司网站制作,google官方下载app,免费下载公众号,云服务器安装win系统做网站题目链接#xff1a;信息学奥赛一本通#xff08;C版#xff09;在线评测系统 (ssoier.cn)
今天刚看完卡尔大哥讲解的01背包#xff0c;今天手敲了一遍#xff0c;还是很多问题#xff0c;只能说自己还是刷题太少或者说是没理解到位。
代码如下
# include iostrea…题目链接信息学奥赛一本通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]是物品的价值 cinmn;memset(dp, 0, sizeof(dp));for(int i 1; i n; i){cinw[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)// {// coutdp[i][j] ;// }// coutendl;//}coutdp[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要当作成员变量的话如果你没初始化那你的数组就是一串乱值。 感悟因为以前看过信奥这个团队讲解的这个题目我今天又按照自己的思路编写了这个代码实际上我还发现这个团队有一点没讲到位就是初始化这一知识点那个团队没有写这个初始化代码虽说这个题目不需要这一段代码也能过但是也是很必要写上的毕竟对于我们这种开始学习动态规划的小白来说最好是写上。
