算法分析
-
状态表示
f[i,j,k]:所有从前i个物品中选,且氧气含量至少是j,氮气含量至少是k的所有选法的气缸重量总和的最小值 -
状态计算：
-
所有不包含物品
i的所有选法：f[i - 1,j,k] -
所有包含物品
i的所有选法：f[i - 1,j - v1,k - v2]
-
注意：即使所需要的氧气或者氮气所需的是数量是负数，但其所需数量与0是等价的，因此可以通过所需数量为0来转移
扩展
可能很多人会有这样的疑问，二维费用的背包问题的状态转移方程代码如下
for(int j = V;j >= v;j --)
for(int k = M;k >= m;k --)
f[j][k] = max(f[j][k], f[j - v][k - m] + w);
而本题的状态转移方程代码如下
for(int j = V;j >= 0;j --)
for(int k = M;k >= 0;k --)
f[j][k] = min(f[j][k], f[max(0, j - v)][max(0, k - m)] + w);
为什么上面的代码 j只需要遍历到v，k只能遍历到m。而下面的代码 j还需要遍历到0，k还需要遍历到0 ？同时为什么氧气或者氮气所需的是数量是负数时，可以与数量0的状态等价？
解答：对比两题的思路，二维费用的背包问题，求的是不能超过体积V，重量M的情况下，能拿到价值的最大值。而本题是至少需要体积V，重量M的情况下，能拿到价值的最小值。就拿体积来说，至少需要多少体积，也就是说有体积比需要的体积大的物品还是能用得到，例如f[3][5]，至少需要3个体积，5个重量，求能拿到价值的最小值，现在只有一个物品，体积是4，重量是4，价值w，它说至少需要3个体积，那么体积是4还是可以用到，只是多了1个体积没用占着而已，不影响其价值。因此若用了这个物品，则变成了求f[0][1] + w，表示体积已经不再需求了，只需要0个体积即可
求最大值最小值初始化总结
二维情况
1、体积至多j，f[i,k] = 0，0 <= i <= n, 0 <= k <= m（只会求价值的最大值）
2、体积恰好j，
$\quad$$\quad$当求价值的最小值：f[0][0] = 0, 其余是INF
$\quad$$\quad$当求价值的最大值：f[0][0] = 0, 其余是-INF
3、体积至少j，f[0][0] = 0，其余是INF（只会求价值的最小值）
一维情况
1、体积至多j，f[i] = 0, 0 <= i <= m（只会求价值的最大值）
2、体积恰好j，
$\quad$$\quad$当求价值的最小值：f[0] = 0, 其余是INF
$\quad$$\quad$当求价值的最大值：f[0] = 0, 其余是-INF
3、体积至少j，f[0] = 0，其余是INF（只会求价值的最小值）
具体参考这篇分享 背包问题中 体积至多是 j ，恰好是 j ，至少是 j 的初始化问题的研究
时间复杂度 $O(nmk)$
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int V1;//氧气
static int V2;//氮气
static int[][] f = new int[30][80];
static int INF = 0x3f3f3f3f;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = reader.readLine().split(" ");
V1 = Integer.parseInt(s1[0]);
V2 = Integer.parseInt(s1[1]);
int n = Integer.parseInt(reader.readLine().trim());
for(int i = 0;i <= 25;i++) Arrays.fill(f[i], INF);
f[0][0] = 0;
for(int i = 1;i <= n;i++)
{
String[] s2 = reader.readLine().split(" ");
int v1 = Integer.parseInt(s2[0]);
int v2 = Integer.parseInt(s2[1]);
int w = Integer.parseInt(s2[2]);
for(int j = V1;j >= 0;j--)
{
for(int k = V2;k >= 0;k--)
{
f[j][k] = Math.min(f[j][k], f[Math.max(0, j - v1)][Math.max(0, k - v2)] + w);
}
}
}
System.out.println(f[V1][V2]);
}
}
因为这题和传统背包的限定不同，背包要求的是能装下，这题要求是至少需要多少。
这道题没有限定的条件，换句话说，只要满足要求，如果最低的质量是1e18，那么他也得拿走
所以，自然不能用传统背包套板子。
牛逼
果然举个例子瞬间就明白了我
豁然开朗
tql
这里是不是只要求至少这种情况
都需要枚举到0
有普通的二维费用背包问题中，$j,k$是不能进行超载的，超过了背包就太重， 背包就 漏 了！
在本题中，是 可以超载 的，理解一下超载是什么意思：
厉害哥！
强悍，顶你上去！
nb!
看懂了 厉害
太屌了吧我敲
大佬。为什么我把 Arrays.fill(f[i],INF);改成 Arrays.fill(f[i],Integer.MAX_VALUE)就会出错呢
因为Integer.MAX_VALUE 加上一个正数它就会爆int变负数了
明白了，谢谢大佬
佬，请问Java中long定义最大值时候该怎么写呢？我试着0x3f写八个要暴红
大佬这句话怎么理解“即使所需要的氧气或者氮气所需的是数量是负数，但其所需数量与0是等价的”
就是在状态转移方程时
f[j][k] = Math.min(f[j][k], f[Math.max(0, j - v1)][Math.max(0, k - v2)] + w);这里，f[j][k]依赖f[j - v1][k - v2]转移，可是可能会有j - v1 < 0或者k - v2 < 0的情况，就是相当于需求量的负数，直接看成0即可import java.util.Scanner;
import java.util.ArrayList;
public class Main{
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int O=input.nextInt();
int N=input.nextInt();
int K=input.nextInt();
}
1、这行
dp[i][j][k] = Math.min(dp[i - 1][t1][t2] + arr[i], dp[i - 1][j][k]);忘记加物品的重量arr[i]2、不要设计为
Integer.MAX_VALUE，因为在这里dp[i - 1][t1][t2] + arr[i]，可能是一个无穷大的数+ arr[i]会爆int变成负数，最好设置为0x3f3f3f3f3、
3重循环中，j和k必须从0开始遍历，因为氧气和氮气没有的情况也需要考虑4、初始化赋值为正无穷大时，必须整个
3纬数组全面赋值为正无穷大，太感谢了大佬，万分感谢
一起加油
冲冲冲
题解已更新，可以再看看
大哥还是大哥理解的更透彻了哈哈哈，希望大哥多写题解，为了大哥这篇题解更完美“因此若了这个物品”，这里加个字，狗头保命
已修改
我认为会不会因为至少二字，因为我们可能实打实去加容器，会超过我们所要求得的部分，我们这里的话相当于对低层次的数据做了一层覆盖？
我认为会不会因为至少二字，因为我们可能实打实去加容器，会超过我们所要求得的部分，我们这里的话相当于对低层次的数据做了一层覆盖？
为啥不用Scanner了？
Scanner也可以的，如果Scanner会超时可以考虑用Bufferdalao nb!
一起努力💪