我要评论描述
一个旅行者有一个最多能装 m 公斤的背包，现在有 n 件物品，它们的重量分别是 w1,w2,...,wn,它们的价值分别为 c1,c2,...,cn，求旅行者能获得最大总价值。
输入描述
第 1 行：两个整数，m （背包容量，m≤200 ）和 n ( 物品数量，n≤30 )。
第 2…n+1 行：每行二个整数 wi,ci，表示每个物品的重量和价值。
输出描述
仅一行，一个数，表示最大总价值。
样例输入
10 4
2 1
3 3
4 5
7 9样例输出
12数据范围与提示
m≤200，n≤30
问题分析
物品编号为i，，背包容量为j ，背包价值为p[i][j]
（1）第一行（i=1）尝试将序号为1的物品放入背包：
背包容量为1时，什么都装不进去背包价值为0，p[1][1]=0。
背包容量为2时，正好1号物品重量为2，背包价值为1，p[1][2]=1。
因为是01背包问题，物品只有一个，所以第一行后面的背包价值都为1。
| 序号i | 背包容量 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 | |
| 重量 | 价值 | |||||||||||
| 1 | 2 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 3 |
|
|
|
|
|
|
|
|
|
|
| 3 | 4 | 5 |
|
|
|
|
|
|
|
|
|
|
| 4 | 7 | 9 |
|
|
|
|
|
|
|
|
|
|
（2）第二行（i=2）尝试将序号为1、2的物品放入背包：
背包容量为1时，什么都装不进去背包价值为0，p[2][1]=0。
背包容量为2时，正好1号物品重量为2，背包价值为1，p[2][2]=1。
背包容量为3时，对比第一行是背包价值为1，即 p[1][2]=1。现新增加了第2种物品，新增加的重量为3，正好为背包容量。因此 p[2][3]=3。
背包容量为4时，也只能放重量为3的物品p[2][4]=3
背包容量为5时，对比第一行是背包价值为1，即 p[1][5]=1。现新增加了第2种物品，背包装上第2种物品后剩余容量为2，正好装第1种物品，因此 p[2][5]=4。p[i][j]=max(p[i-1][j]+第i种物品价值，p[i-1][j])。
| 序号 i | 背包容量 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 | |
| 重量 | 价值 | |||||||||||
| 1 | 2 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 3 | 0 | 1 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 |
| 3 | 4 | 5 |
|
|
|
|
|
|
|
|
|
|
| 4 | 7 | 9 |
|
|
|
|
|
|
|
|
|
|
（2）第三行（i=3）尝试将序号为1、2、4的物品放入背包：
背包容量为1时，什么都装不进去背包价值为0，p[3][1]=0。
背包容量为2时，正好1号物品重量为2，背包价值为1，p[3][2]=1。
背包容量为3时，对比第一行是背包价值为1，即 p[2][3]=3。现新增加了第2种物品，新增加的重量为3，不够背包容量。因此 p[3][3]=3。
背包容量为4时，对比第二行是背包价值为3，即 p[2][4]=3。现新增加了第3种物品，背包装上第3种物品后剩余容量为0，因此 p[3][4]=5。
背包容量为5时，对比第二行是背包价值为4，即 p[2][5]=4。现新增加了第3种物品，背包装上第3种物品后剩余容量为1，装不上其它物品，因此 p[3][5]=5。
背包容量为6时，对比第二行是背包价值为4，即 p[2][6]=4。现新增加了第3种物品，背包装上第3种物品后剩余容量为2，正好撞上1号产品价值为1，因此 p[3][6]=6。
…………………..
依次类推完成表格：
| 序号 i | 背包容量 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 | |
| 重量 | 价值 | |||||||||||
| 1 | 2 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 3 | 0 | 1 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 |
| 3 | 4 | 5 | 0 | 1 | 3 | 5 | 5 | 6 | 8 | 8 | 9 | 9 |
| 4 | 7 | 9 | 0 | 1 | 3 | 5 | 5 | 6 | 9 | 9 | 10 | 12 |
推理：
背包容量为j时，可装入背包的最大价值为：
如果j<第i 物品重量：直接取上方表格背包价值，即p[i][j]= p[i-1][j];
如果j>=第i 物品重量：
p[i][j]=max(第i种物品价值+去掉第i种物品重量后的背包最大价值，p[i-1][j]) = max(第i种物品价值+ p[i-1][j-第i物品价值]，p[i-1][j])
实现代码：
#include <bits/stdc++.h>
using namespace std;
int main(){
int p[201][201] = {},b[201][2] = {} ;//p[201][201]背包价值 b[201][2] 物品重量价值
int m,n; //m 背包容量，n物品数量
cin >> m >> n;
for(int i = 1;i <= n;i++)
{
cin >> b[i][0] >> b[i][1];
}
for(int i = 1;i <=n;i++)
{
for(int j = 1;j <= m;j++)
{
if (j < b[i][0])
{
p[i][j]=p[i-1][j];
}
else
{
int val= j-b[i][0];//去掉第i个物品重量以后背包剩余重量
p[i][j]=max( b[i][1] + p[i-1][val] , p[i-1][j]) ;
}
}
}
cout << p[n][m];
return 0;
}
发表评论