二维费用的背包问题
题目 二维费用的背包问题
思路分析
如果在前面问题的基础上 加上一个限制呢
比如 背包不仅有容积（体积）的限制 还会有重量的限制
加上这么一个维度 代码应该如何变
其实就是和枚举体积一样 再加一个循环 枚举重量即可
代码实现
朴素
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=110;
int v[N],m[N],w[N];//每件物品的体积、重量和价值
int f[N][M][M];
int n,m1,m2;// 物品数量、背包容积上限、背包重量上限
int main()
{
cin>>n>>m1>>m2;
for(int i=1;i<=n;i++)
cin>>v[i]>>m[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j1=0;j1<=m1;j1++){
for(int j2=0;j2<=m2;j2++){//加一层循环即可 状态转移时也要多一
f[i][j1][j2]=f[i-1][j1][j2];
if(j1>=v[i] && j2>=m[i])
f[i][j1][j2]=max(f[i-1][j1][j2],f[i-1][j1-v[i]][j2-m[i]]+w[i]);
}
}
}
cout<<f[n][m1][m2];
return 0;
}
滚动优化
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=110;
int v[N],m[N],w[N];
int f[M][M];
int n,m1,m2;
int main()
{
cin>>n>>m1>>m2;
for(int i=1;i<=n;i++)
cin>>v[i]>>m[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j1=m1;j1>=v[i];j1--){
for(int j2=m2;j2>=m[i];j2--){
f[j1][j2]=max(f[j1][j2],f[j1-v[i]][j2-m[i]]+w[i]);
}
}
}
cout<<f[m1][m2];
return 0;
}
💬 评论