Author: lllyouo
Date: 20250223
tag: 动态规划、背包问题、二维费用背包
link: http://ybt.ssoier.cn:8088/problem_show.php?pid=1271

问题描述

link

分析

记 $a[i],b[i],c[i]$ 分别表示第 $i$ 个气缸的氧气、氮气的量和气缸的重量。$n,x,y$ 分别表示气缸个数、氧气和氮气需求量。

设 $f(i,j,k)$ 表示从前 $i$ 个气缸选择若干个，拥有至少 $j$ 升氧气与 $k$ 升氮气的方案中，气缸总重量最小的方案气缸的总重量。

初始状态 $f(0,0,0)=0$，其余均为正无穷。

考虑第 $i$ 个气缸是否选择：

1. 选：前 $i-1$ 个气缸中至少应该拥有 $max(0,j-a[i])$ 升氧气与 $max(0,k-b[i])$ 升氮气，则 $f(i,j,k)=f(i-1,max(0,j-a[i]),max(0,k-b[i]))+c[i]$
2. 不选：前 $i-1$ 个气缸中至少应该拥有 $j$ 升氧气与 $k$ 升氮气，则 $f(i,j,k)=f(i-1,j,k)$

目标解为：$f(n,x,y)$

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int n, x, y, a[N], b[N], c[N];
int f[N][25][85];

int main() {
	cin >> x >> y >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}
	
	memset(f, 0x3f, sizeof f);
	f[0][0][0] = 0;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= x; j++) {
			for (int k = 0; k <= y; k++) {
				f[i][j][k] = min(f[i - 1][j][k], f[i - 1][max(0, j - a[i])][max(0, k - b[i])] + c[i]); 
			}
		}
	}
	cout << f[n][x][y] << endl;
	
	return 0;
}