P1507NASA食物

这道题是一个01背包的延伸题，只要透彻理解了，就不难了。

这个题有两个T,一个是体积一个是质量，所以这时候我们必须要加一个for了，同时要优化空间(三维降二维），然后用f[j][k]来表示当体积为j,质量为k时的最大价值，加一个for,最后输出即可。

1.再去复习所有背包问题，再去推导方程，注意不同之处

2.j与k不要for到0，for到v[i]或m[i]即可

代码

#include<iostream>

#include<string>

#include<cstring>

#include<cstdio>

#define N 10001

using namespace std;

int dp[][];//当体积为T1,质量为T2时可以装下的

int T1,T2;//体积与质量

int v[],m[],value[];

int n;

int main(){

    scanf("%d%d",&T1,&T2);

    memset(dp,,sizeof(dp));

    scanf("%d",&n);

    for(int i=;i<=n;i++){

        scanf("%d%d%d",&v[i],&m[i],&value[i]);

    }

    for(int i=;i<=n;i++){

        for(int j=T1;j>=v[i];j--){

            for(int k=T2;k>=m[i];k--){

                dp[j][k]=max(dp[j][k],dp[j-v[i]][k-m[i]]+value[i]);

            }

        }

    }

    cout<<dp[T1][T2];    

}

巴特西

P1507NASA食物

最新文章

热门文章