一：题目

给定n(n<=100)种物品和一个背包。物品i的重量是wi，价值为vi，背包的容量为C(C<=1000)。问:应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。

输入格式:
共有n+1行输入： 第一行为n值和c值，表示n件物品和背包容量c； 接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。

输出格式:
输出装入背包中物品的最大总价值。

输入样例:
在这里给出一组输入。例如：

5 10 2 6 2 3 6 5 5 4 4 6

结尾无空行
输出样例:
在这里给出相应的输出。例如：

15

二：思路：

思路：关于如何判断是动态 规划，我个人的理解是
如果所求取的结果是（根据某种规则）跳跃性的挑选数据 那么可以判断为动态规划
本题思路来源 依然是 《算法图解》一书
将背包的容量从1开始展开（设为列），将物品按行展开（设为行），
用二维数组存储 不同容量下的最大价值，每一行只能算上本行和前面的行的物品，二维数组就是网格化的，将一个大问题分解成小问题，

那么其本质就是(递推方程)：（规定容量的基础上）上一个单元格的最大价值 VS（当前商品的价值+剩余容量所存储的价值）

三：来兄弟干了这杯代码

/*思路：关于如何判断是动态 规划，我个人的理解是如果所求取的结果是（根据某种规则）跳跃性的挑选数据 那么可以判断为动态规划本题思路来源 依然是 《算法图解》一书 将背包的容量从1开始展开（设为列），将物品按行展开（设为行），用二维数组存储 不同容量下的最大价值，每一行只能算上本行和前面的行的物品那么其本质就是(递推方程)：（规定容量的基础上）上一个单元格的最大价值 VS（当前商品的价值+剩余容量所存储的价值） */#include<bits/stdc++.h> using namespace std;int main(){int n,c;vector<int>v1,v2;//用v1来存重量，v2来存价值 cin >> n >> c;int MaxVule[n+1][c+1];//物品件为行，背包容量为列（1，2，...c） //将vector容器当中的0为位置占住(因为在二维数组中是从下标为1的开始的)int a1 = 1,a2 = 2;v1.push_back(a1);v2.push_back(a2); for(int i = 1; i <= n; i++){int num1,num2;cin >> num1 >> num2;v1.push_back(num1);v2.push_back(num2);} //二维数组初始化for(int i = 0; i < n+1; i++){for(int j = 0; j < c+1; j++){MaxVule[i][j] = 0;}} // for(int i = 1; i <= n; i++) // cout << v1[i] << ' '; //创建的网格中开始更新数据for(int i = 1; i < n+1; i++){for(int j = 1; j < c+1; j++){if(i == 1){if(v1[i] <= j){MaxVule[i][j] = v2[i]; }}else{//比较上一个单元格的价值 如果比其大就更新//计算本单元格的价值 = 商品的价值 + 剩余空间的价值int value = j - v1[i];if(value >= 0) {int temp = v2[i] + MaxVule[i-1][value];//注意i-1 因为本行已经装进商品了不可重复装入 if(MaxVule[i-1][j] < temp){MaxVule[i][j] = temp;}else{MaxVule[i][j] = MaxVule[i-1][j];} }else{//若商品重量大于 j,则直接继承上一个单元格 MaxVule[i][j] = MaxVule[i-1][j]; }}}} // for(int i = 1; i <= 3; i++){ // for(int j = 1; j <= 4; j++){ // // cout << MaxVule[i][j] << ' '; // } // cout << endl; // }cout << MaxVule[n][c]; } //5 10 //2 6 //2 3 //6 5 //5 4 //4 6//3 4 //1 1500 //4 3000 //3 2000

四：知识速递（如果对本题的vector容器不熟悉的可以学一下哈）

vector的基本用法

加油！陌生的你，You are the best boy!!!

总结

以上是生活随笔为你收集整理的7-6 0-1背包 (20 分)(思路加详解+网格做法+动态规划)Come Baby !!!!!!!!!!!!!!的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。