传送
01背包又进化了，它变成了二维背包。
既然它多了一个维度，那么我们的f[j]也变成了二维数组f[i][j]，其中i表示费用1，j表示费用2
核心方程也相应的变成了f[i][j]=max(f[i-v1[i]][j-v2[i]],f[i][j]),同时，也多了一层循环
代码如下：
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int h,n,m,f[5001][5001],v[51],w[51],o[51]; int main() { cin>>h>>m; cin>>n; for(int i=1;i<=n;i++) {cin>>o[i]>>w[i]>>v[i]; } for(int i=1;i<=n;i++) { for(int j=h;j>=o[i];j--) { for(int k=m;k>=w[i];k--) {f[j][k]=max(f[j][k],f[j-o[i]][k-w[i]]+v[i]); } } } cout<<f[h][m]; }
转载于:https://www.cnblogs.com/lcez56jsy/p/10507002.html
相关资源：数据结构—成绩单生成器