二维费用背包问题_二维费用的背包问题

一、问题

二、思路

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

1、状态表示

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

2、状态转移

f ( i , j , k ) = { f ( i − 1 , j , k ) m a x ( 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、循环设计

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

4、注意

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

三、代码

#include<iostream>
#include<cstring>
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<<f[v][m]<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29