【二维背包】AcWing1020.潜水员题解

题意

题目链接：1020. 潜水员 - AcWing题库
你需要m的氧气，n的氮气，在你面前有若干个瓶子（里面装氧气和氮气），每个瓶子都有质量，求满足你需要的条件下，最少重量是多少，例如：

3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

你需要5的氧气和60的氮气，最少情况下是249，选择1，2或者4，5号气缸。
数据范围：
$1≤m≤21,$
$1≤n≤79,$
$1≤k≤1000,$
$1≤a_i≤21,$
$1≤b_i≤79,$
$1≤c_i≤800$

思路

二维背包肯定是f[i][j],但是这里不同的地方在于，这是一个范围，比如我可以一个瓶子可以有很多氧气和氮气，但是重量有很少...
所以这个时候f[i][j]不是我们表示的获得i的氧气和j的氮气，我一开始想的是大于[m,n]的话直接算[m,n]但是好像没做出来，我觉得是可做的...

这样来看f[i][j][k](实际上就是二维)的定义是：前i个物品里面选，且氧气含量至少是j，氮气含量至少是k，的最小重量。

上面是y总的定义，我们可以这么看：考虑前i个物品，氧气体积大于等于j，氮气体积大于等于k的方案

可以按照“是否选择第i个物品”来划分
1）若不选择第i个物品
则就是“考虑前i-1个物品，氧气体积大于等于j 并且氮气体积大于等于k的方案”的集合 (f[i-1][j][k])

2）若选择了第i个物品
由于该集合均包含第i个物品，假设第i个物品有v1个氧气 v2个氮气
则除去第i个物品
就是考虑“从前i-1个物品选 氧气体积大于等于j-v1 氮气体积大于等于k-v2的方案”的集合
若j-v1小于零的话：就说明第i个物品提供的氧气已经足够,不需要从前i-1个物品中获得任何氧气
因此当j-v1小于零的时候,直接按照0考虑即可,氮气也一样

代码

inline void Case_Test()
{
    cin>>V>>M>>n;
    mem(dp,0x3f);
    dp[0][0]=0;
    for (int i=1;i<=n;i++)
    {
        cin>>v>>m>>w;
        for (int j=V;j>=0;j--)
            for (int k=M;k>=0;k--)
                dp[j][k]=Min(dp[j][k],dp[Max(0,j-v)][Max(0,k-m)]+w);
    }
    cout<<dp[V][M];
}