【洛谷p1507】NASA的食物计划

（一次a……）

好的上算法标签：

嗯这是个二维背包

（万年不变分隔线）

二维的题就是在一维基础上增加了一个条件，这个背包不仅含有质量还有体积。所以我们增加一层循环。核心算法：

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

        for(int j=m;j>=zl[i];j--)

            for(int k=v;k>=tj[i];k--)

                f[i][j][k]=max([f[i-][j][k],f[i-][j-z1[i]][k-v1[i]]+c[i]);

降二维节省空间：

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

        for(int j=m;j>=zl[i];j--)

            for(int k=v;k>=tj[i];k--)

                f[j][k]=max([f[j][k],f[j-z1[i]][k-v1[i]]+c[i]);

好的扯回原题：nasa的食物计划

ac代码如下：（懒得写解释）

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<string>

#include<cmath>

using namespace std;

int v,m;

int n;

int tj[],zl[],dgc[];

int f[][];

int main()

{

    cin>>v>>m>>n;

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

    cin>>tj[i]>>zl[i]>>dgc[i];

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

        for(int j=m;j>=zl[i];j--)

            for(int k=v;k>=tj[i];k--)

                f[j][k]=max(f[j][k],f[j-zl[i]][k-tj[i]]+dgc[i]);

    cout<<f[m][v];

}

end-

巴特西

【洛谷p1507】NASA的食物计划

最新文章

热门文章