思路
**全部采用一维数组
此题涉及数量 比常见的0-1背包 多了一层循环
采用逆序 **
f[j]=max(f[j],f[j-v[i]*k]+w[i]*k);
采用二维的话 状态转移方程 f[i][j]=max(f[i-1][j]+f[i-1][j-v[i]*k]+w[i]*k)
其实 上一层的f[i][j]已经存储了 不必采用二维空间进行存储
解释下为何采用逆序
常见的0-1背包 懂了逆序后面就好做了
假如枚举到:i = 3, j = 8, v[3] = 5, w[3] = 1
二维:dp[3][8] = max(dp[2][8], dp[2][3] + w[3]) 此时的dp[2][8]和dp[2][3]都是上一轮的状态值
一维:dp[8] = max(dp[8], dp[3] + w[3]) 我们要保证dp[8]和dp[3]都是上一轮的状态值
按照逆序的顺序,一维dp数组的更新顺序为:dp[8], dp[7], dp[6], ... , dp[3]
也就是说,在本轮更新的值,不会影响本轮中其他未更新的值!较小的index对应的状态是上一轮的状态值!
如果按照顺序进行更新,dp[3] = max(dp[3], dp[0] + w[0]),对dp[3]的状态进行了更新,那么在更新dp[8]时,用到的dp[3]
就不是上一轮的状态了,不满足动态规划的要求。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
int f[N];
int n,v1;
int v[N],w[N],s[N];
int main(){
cin>>n>>v1;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++)
for(int j=v1;j>=0;j--)//逆序
for(int k=s[i];k>=0;k--)
{
if(v[i]*k<=j)
f[j]=max(f[j],f[j-v[i]*k]+w[i]*k);
}
cout<<f[v1]<<endl;
return 0;
}