分析
完全背包问题与01背包的一个不同点就是,完全背包问题中一个物品在不超过背包体积的情况下,可以无限用。
与01背包相比,只有一个小小的变化,我们也可以引用01背包问题的思路
- dp[ i ] :表示当前背包体积时,物品的最大价值
- 状态转移方程:max(dp[ j ], dp[ j - V[ i ]] + W[ i ])
与01背包相比,改进的地方
因为需要考虑无限放的问题,就可以从前向后遍历。这样我们在每一个体积的时候,看上去值减去了一个物品的重量,但是我们是从前向后的,我们在后面的每一次状态,其实就可以看成是一个迭代的的过程。他是在前面已经选择该物品的前提下,再选一次这个物品。
#include <iostream>
using namespace std;
const int N = 1010;
int dp[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
int v,w;
cin>>v>>w;//v 物品体积 w 物品重量
for(int j = v; j <= m; j++)
dp[j] = max(dp[j], dp[j - v] + w);
}
cout<<dp[m]<<endl;
return 0;
}