二维费用背包问题

• 一、问题
• 二、思路
• • 1、状态表示
  • 2、状态转移
  • 3、循环设计
  • 4、注意
• 三、代码

一、问题

二、思路

这道题归根结底还是背包问题的一种，面对背包问题，我们的思路就是面对前i个物品的时候，我们的第i个物品是选还是不选，如果条件允许的话，我们在二者之间选出一个最大值。

1、状态表示

f[i][j][k]f[i][j][k]f[i][j][k]面对前iii个物品，容量是jjj，承受重量是kkk的时候，我们所能携带的物品的最大价值。

2、状态转移

f(i,j,k)={f(i−1,j,k)max(f(i,j−v[i],k−m[i])+w[i],f(i−1,j,k))j≥v[i]&&k≥m[i]f(i,j,k)= \begin{cases} f(i-1,j,k)\\ max\big(f(i,j-v[i],k-m[i])+w[i],f(i-1,j,k)\big)&j\geq v[i]\&\&k\geq m[i] \end{cases} f(i,j,k)={f(i−1,j,k)max(f(i,j−v[i],k−m[i])+w[i],f(i−1,j,k))​j≥v[i]&&k≥m[i]​

3、循环设计

三重循环即可，背包问题我们一般是把物品iii放在最外层循环，这样做的话，我们方便对空间进行优化。对于剩余的两个限制条件之间的循环顺序是无关紧要的。

4、注意

由于多重限制条件的存在，我们的f数组开到了3维，如果数据范围很大的话，可能没有办法开那么大的空间，因此，对于二维费用背包问题我们一般使用的是空间优化后的版本。

三、代码

#include
#include
using namespace std;
const int N=1010;
int a[N],b[N],c[N],f[N][N];
int n,v,m;
int main()
{cin>>n>>v>>m;for(int i=1;i<=n;i++){scanf("%d%d%d",a+i,b+i,c+i);}for(int i=1;i<=n;i++){for(int j=v;j>=0;j--){for(int k=m;k>=0;k--){if(a[i]<=j&&b[i]<=k){f[j][k]=max(f[j-a[i]][k-b[i]]+c[i],f[j][k]);}}}}cout<