背包模型 二维费用的背包问题

昨天写了一个皮卡丘的题。也是二维费用的背包问题。我用那题的思路写了下面的代码。过不去样例。没事。我本来就是要写不出这题的。

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;const int M=110;
int f[M][M];
int V1,V2;
int n;int main(){scanf("%d%d%d",&n,&V1,&V2);for(int i=0;i<n;i++){int v1,v2,w;scanf("%d%d%d",&v1,&v1,&w);for(int j=V1;j>=v1;j--){for(int k=V2;k>=v2;k--){f[j][k]=max(f[j][k],f[j-v1][k-v2]+w);}}}printf("%d\n",f[V1][V2]);return 0;
}

发现上面出错是因为敲错了一个字母。改了之后就过了。确实比较简单。

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;const int M=110;
int f[M][M];
int V1,V2;
int n;int main(){scanf("%d%d%d",&n,&V1,&V2);for(int i=0;i<n;i++){int v1,v2,w;scanf("%d%d%d",&v1,&v2,&w);for(int j=V1;j>=v1;j--){for(int k=V2;k>=v2;k--){f[j][k]=max(f[j][k],f[j-v1][k-v2]+w);}}}printf("%d\n",f[V1][V2]);return 0;
}