01背包问题

01背包问题指的是在容量有限的背包中装下总价值最大的物品，并且每种物品只能使用一次。所以每个物品都有两种选择，放进背包和不放进背包。我们可以将每种情况都模拟一遍，将结果取最大值。但是这种方法时间复杂度太高了，所以不可取。在考虑第i个物体取还是不取时，如果有几种方案体积是一样的，我们只要取总收益最大的那种方案就行了.所以，我们可以把考虑了前i个物品以后，总体积为0~n时的最优方案都记下来。现在只需要考虑一下第i个物品取的收益更大，还是不取的收益更大。这个可以用一行代码来计算f[i][j]=max(f[i-1][j],f(i-1)[j-w[i]]+v[i]);其中i为背包中物品的个数，j是背包中的重量。所以当i=n,j=w时就可以得出最大值。 最后附上简单易懂的视频讲解：https://www.bilibili.com/video/BV1g7411B7SP?from=search&seid=9910345648741816891&spm_id_from=333.337.0.0

#include <iostream>
using namespace std;
int p[1010][1010],p1[1010],p2[1010];
int main()
{
	int n,m,i,j;
	cin >> n >> m;//n代表背包所装的最大物品数，m为最大重量
	for(i=1;i<=n;i++){
		scanf("%d %d",&p1[i],&p2[i]);
}
	for(i=1;i<=n;i++){
		for(j=0;j<=m;j++){
           p[i][j] = p[i - 1][j];//   当j<p1时说明背包装不下，j++  
		   if(j>=p1[i])  
                p[i][j] = max(p[i - 1][j], p[i-1][j - p1[i]] + p2[i]);
}
}
    printf("%d",p[n][m]);
	return 0;
}