算法思路
理解题意
二维$01$背包问题:
- 限制:
- 氧气数量
- 氮气数量
- 目标:
Min总重
注意: 这里的限制条件是不小于要求的氧气/氮气数量; 重量最小. 可以看作是一般$01$背包的翻转.
$DP$分析
思路1
状态定义 dp(i, j, k)
-
集合: 从前$i$罐气缸中选择, 且氧气数量 恰好 为$j$、氮气数量 恰好 为$k$的所有选法.
-
属性:
Min
状态计算
根据第$i$个气罐是否选择划分集合:
-
不选择, 集合等价于从前$i$罐气缸中选择, 且氧气数量恰好为$j$、氮气数量恰好为$k$的所有选法, 对应集合
的最小值: $dp(i-1, j, k)$ -
选择, 确定部分: 带来重量$m_i$, 以及氧气和氮气的体积$v1_i$和$v2_i$; 不确定部分: 等价于集合从前$i-1$
且氧气数量恰好为$j-v1_i$、氮气数量恰好为$k-v2_i$的所有选法, 对应集合的最小值: $dp(i-1, j-v1_i, k-v2_i)$.
状态的属性为Min: $dp(i,j,k) = min\lbrace dp(i-1,j,k), dp(i-1,j-v1_i,j-v2_i)+m_i\rbrace$
代码实现
状态定义相比于传统$01$背包带来的不同: 恰好vs不超过, 给实现带来的影响是初始化的不同. 实际上
两者的初始化都是根据其状态定义出发的.
-
不超过: $dp(0,j,k) = 0$, 因为前$0$个物品其对应两个限制均为$0$, 而对任意$j、k$, $0\le j \& 0\le k$.
-
恰好: 仅$dp(0,0,0) = 0$. 因为只有对$j = 0 \& k = 0$时才满足 恰好 的定义.
具体在计算过程中不能考虑集合为$\varnothing$的情况, 本题中求的是Min, 所以除$dp(0,0,0)$外,
其他状态的初始值设为$+\infty$.
具体代码:
无具体代码, 因为这种思路是无法AC的. Mua ha ha ha ha!…
考虑一种极端情况: 如果每个气罐的氧气含量为1, 氮气含量为79, 那么氮气最大需靠考虑$29 \times79$;
对于氧气同样如此, 那么状态转移需要考虑$1000\times (29\times 79)^2$, 超时.
思路2
状态定义$dp(i, j, k)$
-
集合: 从前$i$罐气缸中选择, 且氧气数量 至少 为$j$、氮气数量 至少 为$k$的所有选法.
-
属性:
Min
状态计算
根据第$i$个气罐是否选择划分集合:
-
不选择, 集合等价于从前$i$罐气缸中选择, 且氧气数量至少为$j$、氮气数量至少为$k$的所有选法, 对应集合
的最小值: $dp(i-1, j, k)$ -
选择, 确定部分: 带来重量$m_i$, 以及氧气和氮气的体积$v1_i$和$v2_i$; 不确定部分: 等价于集合从前$i-1$
且氧气数量至少为$j-v1_i$、氮气数量至少为$k-v2_i$的所有选法, 对应集合的最小值: $dp(i-1, j-v1_i, k-v2_i)$.
状态的属性为Min: $dp(i,j,k) = min\lbrace dp(i-1,j,k), dp(i-1,j-v1_i,j-v2_i)+m_i\rbrace$
到目前为止, 至少和恰好的分析相同. 不同之处在具体实现上.
具体实现
-
初始化: $dp(0, 0, 0) = 0$, 其余对应$\varnothing$, 值可以设为$+\infty$. 从定义出发, 什么都不选对应
氧气和氮气的数量均为$0$, 而只有$j=0\&k=0$时有$0\ge j\& 0\ge k$. -
氧气和氮气可以为负数: 以氧气为例, 如果某个状态氧气为负数表明氧气数量足够且有剩余;
从状态的定义出发或许更好理解: 假设某种选法的氧气数量为$j$, 对于任意的$j$其一定
至少($\ge$)一个负数,即使是什么都没选都满足! -
负数的状态可以均视为$0$: 含义相同, 即表示氧气
/氮气已经足够, 前$i-1$个气罐不需要再选择
氧气/氮气. 所以在具体实现时$j$可以小于$v1_i$(第$i$罐氧气数量), 否则我们会遗漏某些合法状态.
代码实现
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int V1 = 22, V2 = 80;
int v1, v2, n;
int dp[V1][V2];
int main()
{
memset(dp, 0x3f, sizeof dp);
dp[0][0] = 0;
cin >> v1 >> v2 >> n;
for( int i = 1; i <= n; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
for( int j = v1; j >= 0; j -- )
for( int k = v2; k >= 0; k -- )
dp[j][k] = min( dp[j][k], dp[max(0, j - a)][max(0, k - b)] + c );
}
cout << dp[v1][v2] << endl;
return 0;
}
小小结
上述三种状态定义的区别:
-
初始化: 根据定义出发, 区分合法的状态和不合法的, 而不合法状态对应$\varnothing$, 根据题目不同要求
赋值以保证计算过程中不会使用. -
合法状态: 对于
最多和恰好, 其状态均为非负数; 对于至少没有要求.
