01背包问题 c/c 实现01背包问题问题描述输入描述输出描述输入示例示例代码1示例代码2使用一维滚动数组从右到左遍历01背包问题问题描述小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的空间并且具有不同的价值。小明的行李空间为 N问小明应该如何抉择才能携带最大价值的研究材料每种研究材料只能选择一次并且只有选与不选两种选择不能进行切割。输入描述第一行包含两个正整数第一个整数 M 代表研究材料的种类第二个正整数 N代表小明的行李空间。第二行包含 M 个正整数代表每种研究材料的所占空间。第三行包含 M 个正整数代表每种研究材料的价值。输出描述输出一个整数代表小明能够携带的研究材料的最大价值。输入示例6 12 2 3 1 5 22 3 1 5 4 3示例代码1#includeiostream#includevectorusingnamespacestd;intmain(){// M 代表物品种类// N 代表01背包容量intM0,N0;while(cinMN){//定义 (M1) * (N1) 的数组 dp[i][j] 代表背包容量为j从1-i(不从0开始从1开始)物品中的最大价值vectorvectorintdp(M1,vectorint(N1,0));// dp[M][N] 即为所求从1-M当中在背包容量为N的最大价值//定义物品重量vectorintweight(M1,0);//定义物品价值vectorintvalue(M1,0);//输入for(inti1;iM;i){cinweight[i];}for(inti1;iM;i){cinvalue[i];}//遍历dp 从上到下从左到右for(inti1;iM;i){for(intj1;jN;j){//当前背包容量可以装第i件物品看看装的价值大还是不装的价值大取价值大的if(weight[i]j){dp[i][j]max(dp[i-1][j],value[i]dp[i-1][j-weight[i]]);//装不下}else{dp[i][j]dp[i-1][j];}}}}return0;}示例代码2使用一维滚动数组从右到左遍历#includeiostream#includevectorusingnamespacestd;intmain(){// M 代表物品种类// N 代表01背包容量intM0,N0;while(cinMN){vectorintdp(M1,0);//定义物品重量vectorintweight(M1,0);//定义物品价值vectorintvalue(M1,0);//输入for(inti1;iM;i){cinweight[i];}for(inti1;iM;i){cinvalue[i];}//遍历dp 从上到下从右到左for(inti1;iM;i){for(intjN;jweight[i];j--){dp[j]max(dp[j],value[i]dp[j-weight[i]]);}}coutdp[N]endl;}return0;}