目录
题目：
题解：
图表解析：
详细例子：
题目：
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。输入格式：
第一行两个整数，N，V ，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi,用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式：
输出一个整数，表示最大价值。
数据范围：
0<N,V≤1000
0<vi,wi≤1000输入样例：
4 5
1 2
2 4
3 4
4 5输出样例：
8
题解：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1005;
int v[N]; //体积
int w[N]; //价值
int f[N][N]; //f[i][j], j体积下前i个物品的最大价值
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> v[i] >> w[i];
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(j < v[i])
{
//如果当前背包容量小于第i个物品的体积，那最大价值就是前i-1个物品里面选的最大价值
f[i][j] = f[i - 1][j];
}
else
{ //如果能装得下第i个物品，就判断一下选和不选第i个物品哪个最大价值大
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
}
}
cout << f[n][m] << endl;
return 0;
}
图表解析：
如图所示：该二维数组第一行代表只从前1个物品中选，背包容量是1,2,3,4,5情况下的最大价值。第一个物品的体积是1，价值是2。所以在只从前1个物品里面选的情况下，无论后面背包容量是多少，最大价值都只是把第一个物品放进背包，所以第一行的最大价值就是2。所以其实该二维数组存的就是在背包容量是j的情况下从前i个物品里面选的最大价值。可以看成一个总问题，但其实这个数组里面记录了所有子问题的解。每一个更大的问题都是在子问题的基础上推导而来。
小tips：如果数组声明为全局变量，那么默认里面全都是0。如果初始在主函数里面，那么里面的值是随机数垃圾数据。所以本题不需要初始化行等于0或者列等于0的情况，里面默认都是0了，在背包容量为j,从前零个物品里面选或者背包容量为0,从前i个物品里面选这两种情况的最大价值肯定是0。
推导过程：始终从第一个物品开始决策选还是不选该物品，然后存下当前情况下的最大价值。
如果背包容量小于当前待决策物品的体积，那么肯定是放不下的，所以最大价值就是当前背包容量下，从前i-1个物品里面选的最大价值。
如果能放下，就从选或者不选这两种情况里面选最大价值的情况。
先说不选的，不选的话就是从前i-1个物品里面选，且背包容量就是当前的j情况下的最大价值。
如果选，那么就是背包容量减去要选的物品的体积，且从前i-1个物品里面选出来的最大价值再加上第i个物品的价值。因为这样才能确保第i个物品能放的进去。
最后输出二维数组右下角的数据即为题目所求。
详细例子：
文章来源：https://www.toymoban.com/news/detail-773693.html
比如在判断f[3][5]时，即：在背包容量是5，从前三个物品里面选时，最大价值是什么。就要决定一下是否选择第三个物品，如果不选第三个物品，就是背包容量为5，从前两个物品里面选的最大价值，即f[2][5]，如果选，那就得先把第三个物品的空间腾出来，也就是5减去第三个物品的体积3，也就是从前两个物品里面选，背包容量是2的情况下的最大价值再加上第三件物品的价值4，也就是4+4=8。然后看看这两种做法哪种最大价值最大，显然8>6,所以要选第三件物品。文章来源地址https://www.toymoban.com/news/detail-773693.html
到了这里，关于01背包问题（动态规划）（详细图解）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
