P1507 NASA的食物计划

· · 个人记录

P1507 NASA的食物计划

普通01背包，就是多加了一个条件。

#include<iostream>
using namespace std;
struct g
{
    int u,w,k;
}a[55];
int n,m,x,f[405][405];
int main()
{
    cin>>n>>m>>x;
    for(int i=1;i<=x;i++)
    {
        cin>>a[i].u>>a[i].w>>a[i].k;
    }
    for(int i=1;i<=x;i++)
    {
        for(int j=n;j>=a[i].u;j--)
        {
            for (int k=m;k>=a[i].w;k--)
            {
                if(j>=a[i].u&&k>=a[i].w)f[j][k]=max(f[j][k],f[j-a[i].u][k-a[i].w]+a[i].k);
                else f[j][k]=f[j][k];
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}