[Acwing] 二维费用背包问题

前言

传送门 : https://www.acwing.com/problem/content/8/ 貌似之前就做过了 (地下城的 HP和护甲值)

思路

原先 01 01 01背包的状态转移方程是

f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v [ i ] ] + w [ i ] ) f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]) f[i][j]=max(f[i−1][j],f[i−1][j−v[i]]+w[i])

选在容量为 j j j的情况下选前 i i i件物品的选法

既然多加了一维 并且这维 和 体积是同一属性的 那么 状态转移方程应该是

f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] [ k ] , f [ i − 1 ] [ j − v ] [ k − m ] + w [ i ] ) f[i][j] = max(f[i-1][j][k],f[i-1][j-v][k-m]+w[i]) f[i][j]=max(f[i−1][j][k],f[i−1][j−v][k−m]+w[i])

优化 : 因为都只是用了到 i − 1 i-1 i−1层 所以我们可以删除该层

但是为了不影响答案,我们需要从大到小枚举

因此优化后的状态转移方程为 f [ j ] [ k ] = m a x ( f [ k ] [ m ] , [ j − v ] [ k − m ] + w [ i ] ) f[j][k] = max(f[k][m],[j-v][k-m]+w[i]) f[j][k]=max(f[k][m],[j−v][k−m]+w[i])

CODE

#include 
using namespace std;
const int N = 1010;
int f[N][N];
int n,V,M;
int v[N],m[N],w[N];

void solve()
{
    cin>>n>>V>>M;
    for(int i=1;i>v[i]>>m[i]>>w[i];

    for(int i=1;i=v[i];j--)
            for(int k=M;k>=m[i];k--)
            f[j][k] =max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);
    cout