三维变二维的优化

二维费用背包

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1010, M = 110;
int n,m,x;
int w[N],v[N],q[N];
int f[N][N];
int main()
{
    cin>>n>>m>>x;
    for (int i=1;i<=n;i++) cin>>v[i]>>q[i]>>w[i];
    for (int i=1;i<=n;i++)
        for (int j=m;j>=v[i];j--)
            for (int k=x;k>=q[i];k--)
                f[j][k]=max(f[j][k],f[j-v[i]][k-q[i]]+w[i]);
    cout<<f[m][x]<<endl;
    return 0;
}