描述
一个旅行者有一个最多能装 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])文章来源：https://www.toymoban.com/news/detail-861527.html
实现代码：文章来源地址https://www.toymoban.com/news/detail-861527.html
#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;
}
到了这里，关于动态规划_01背包问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
