1020. 潜水员 - AcWing题库

• 二维费用的背包问题，求最小

分析

• 条件：需求氧气 M M M ，需求氮气 N N N ，氧气瓶的个数 K K K，需求特定数量的氧和氮

• 集合：所有从前 i i i 个物品中选，总氧气 = j = j =j ，总氮气 = k = k =k 的所有选法的集合

• 属性： M i n ( w ) Min(w) Min(w)

• 状态表示：设 f [ i , j , k ] f[i,j,k] f[i,j,k] 为从前 i i i 个物品中选，总氧气 = j =j =j ，总氮气 = k =k =k 选出物品的最小价值（氧气瓶的重量）

• 状态计算： f [ i , j , k ] = m i n ( f [ i − 1 , j , k ] , f [ i − 1 , j − v [ i ] , k − m [ i ] ] + w [ i ] ) f[i,j,k]=min(f[i-1,j,k],f[i-1,j-v[i],k-m[i]]+w[i]) f[i,j,k]=min(f[i−1,j,k],f[i−1,j−v[i],k−m[i]]+w[i])

  • 表示不选或者选第 i i i 个物品

• 求最后一步： a n s = f [ K , M , N ] ans=f[K,M,N] ans=f[K,M,N]

实现细节

• 当要求 ≤ \le ≤ 的时候， f f f 的初始化为 f [ 0 , j , k ] = 0 f[0,j,k]=0 f[0,j,k]=0

• 当要求 ≥ \ge ≥ 的时候， f f f 的初始化为 f [ 0 , 0 , 0 ] = 0 , f [ o t h e r s ] = i n f f[0,0,0]=0,f[others]=inf f[0,0,0]=0,f[others]=inf

• 注意，每个物品对氧气和氮气的贡献的范围是 M → 0 , N → 0 M\to 0,N\to 0 M→0,N→0

• 要保证数组不越界

Code

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1500;

int m, n, K;
int f[maxn][maxn];
int main() {
	scanf("%d%d%d", &m, &n, &K);
	for(int i = 0; i <= 1300; i++)
		for(int j = 0; j <= 1300; j++)
			f[i][j] = inf;
	f[0][0]=0;
	for(int i = 0; i < K; i++) {
		int vol1, vol2, w;
		scanf("%d%d%d", &vol1, &vol2, &w);
		for(int j = m; j >= 0; j--) { //贡献最小可以为0
			for(int k = n; k >= 0; k--) {
				f[j][k] = min(f[j][k], f[max(0,j - vol1)][max(0,k - vol2)] + w);
			}
		}
	}
	
	printf("%d\n",f[m][n]); 

	return 0;
}