[数据结构与算法]AcWing 1020. 潜水员（二维费用01背包问题变形）

题目描述：

一共有 k 种 物品（气缸），对于第 i 种物品，第一维 费用（氧气体积） 是 v1i，第二维 费用（氮气体积） 是 v2i，价值（气缸重量） 是 wi
每个物品只能 被选一次

求一个 选择方案，使得第一维费用 至少为 n，第二维费用 至少为 m 且 总价值最小

思路：

闫氏dp分析法：

状态表示dp[i,j,k]:
集合：所有从前i个物品中选，且氧气含量至少是j，氮气含量至少是k的所有选法
属性：所有从前i个物品中选，且氧气含量至少是j，氮气含量至少是k的所有选法的气缸重量总和的最小值

状态计算：
所有 不包含物品i 的所有选法：dp[i - 1, j, k]
所有 包含物品i 的所有选法：dp[i - 1, j - ai, k - bi]
因此，状态转移方程：dp[j, k] = min(dp[j, k], dp[max(0, j - ai), max(0, k - bi)] + ci); (省去第一维)

细节处理：

（1）
初始化的细节处理：（对于要求体积 “至少是” 问题的初始化处理）
①dp(0)(0)(0)=0：第一维为0(一件物品都不选)，第二维和第三维体积均为0(氧气和氮气体积至少为0),
这种情况是合法的，且min值为0。
②dp(0)(1,2,3...)(1,2,3...)：第一维为0(一件物品都不选)，第二维和第三维体积至少为i(1,2,3…)，
根据实际，这些状态都是不合法的(无法求min)，因此将它们初始化为 ∞ 即可(至于是＋∞还是－∞取决于这个问题是求
的最大值还是最小值)

（2）
即使所需要的氧气或者氮气所需的是数量是负数，但其所需数量与0是等价的，因此可以通过所需数量为0来转移,举个例子:体积至少为-2, 这种情况是存在的，体积是0，至少是-2，体积是10，至少也是-2。
因此：j需要遍历到0，k 需要遍历到 0。

时间复杂度：

$O(nmk)$

代码：

#include<bits/stdc++.h>

using namespace std;

int n,m;
int k;
int ai,bi,ci;//第 i 个气缸里的氧和氮的容量及气缸重量
const int N = 22,M = 80;//氧,氮各自需要的量数据范围 
int dp[N][M];

int main()
{
	cin>>m>>n;
	cin>>k;
	//初始化 
	memset(dp,0x3f,sizeof dp);
//其它的所有方案(f[0][1,2,3...]),由于第一维为0(一件物品都不选),所以第二维体积必须为0不能为i(1,2,3...),
//这些状态都是不合法的,因此将它们初始化为∞即可
	dp[0][0]=0;
//第一维为0(一件物品都不选,代码中第一维),第二维体积为0此时只有f[0][0]是合法的
	
	for(int i=0;i<k;++i)
	{
		cin>>ai>>bi>>ci;
		for(int j=m;j>=0;--j)
		{
			for(int k=n;k>=0;--k)
			{
				dp[j][k]=min(dp[j][k],dp[max(0,j-ai)][max(0,k-bi)]+ci);
//这两维体积可以为负,此时置为0即可。举个例子:体积至少为-2,这种情况是存在的,体积是5,至少是-2,体积是10,
//至少也是-2
			}
		}
	}
	cout<<dp[m][n]<<endl;
//所有从前i个物品中选,且氧气含量至少是j, 氮气含量至少是k 的所有选法中 所需的气缸的重量总和的最低值
	return 0;
}

扩展：

求对于三类最大值最小值题型的初始化总结

• 一、 体积最多是j（对应背包问题模板题）

• • dp数组全初始化为0

• • ①二维：f[i,k] = 0，0 <= i <= n, 0 <= k <= m（只会求价值的最大值）

• • ②一维：f[i] = 0, 0 <= i <= m（只会求价值的最大值）

• • 从实际含义进行推理，f[0,i]表示：一件物品都不选的情况下，体积最多为i时的最大价值，i不管取多少，什么都不选是一种方案，每个f[0,i]至少包含一个方案，f[0,i]的最大值为0。

• 二、 体积恰好是j

• • dp(0)=0，dp(1,2,3...) = ∞，并保证V>=0

• • ①二维：

• • 当求价值的最小值：f[0][0] = 0, 其余是inf
• • 当求价值的最大值：f[0][0] = 0, 其余是-inf

• • ②一维：

• • 当求价值的最小值：f[0] = 0, 其余是inf
• • 当求价值的最大值：f[0] = 0, 其余是-inf
• • 此时，就只有f[0][0]是合法的，其它的所有方案（f[0][1,2,3...]），由于一件物品都不选，所以体积必须为0不能为i，这样的状态都是不合法的，因此将它们初始化为∞即可，至于是＋∞还是－∞则取决于这个问题是求的最大值还是最小值。

• 三、 体积至少为j

• • dp(0)=0，dp(1,2,3...)=∞，无需保证V>=0

• • ①二维：体积至少j，f[0][0] = 0，其余是inf（只会求价值的最小值）

• • ②一维：体积至少j，f[0] = 0，其余是inf（只会求价值的最小值）

• • 状态计算与第二种相同，只不过V可以为负，此时置为0即可。