蓝桥杯Java ABC组 AcWing P1020 潜水员

题目链接：
https://www.acwing.com/problem/content/1022/

#二维背包 #Model #Favorite

思路

好题！

可以让你思考各种背包问题中，对体积的定义不同，则初始化就不同

本题求的是是至少需要体积 V V V，重量 M M M 的情况下，能拿到价值的最小值。

就拿体积来说，至少需要多少体积，也就是说有体积比需要的体积大的物品还是能用得到，例如 f[3][5]，至少需要 3 个体积，5 个重量，求能拿到价值的最小值，现在只有一个物品，体积是 4，重量是 4，价值 w w w，它说至少需要 3 个体积，那么体积是 4 还是可以用到，只是多了 1 个体积没用占着而已，不影响其价值，此时 f[-1][1] 这个状态是合法的。

因此若用了这个物品，则变成了求 f[0][1] + w，表示体积已经不再需求了，只需要 0 个体积即可。

f[0][i] 代表的意思是体积大于等于 0，重量大于等于 i 时价值的最小值

可以认为在至少的语义上，物品的体积上限是没有限制的，反而是物品体积的下限需要有限制

下面是总结：

求最大值最小值初始化总结
二维情况
1、体积至多j，f[i,k] = 0，0 <= i <= n, 0 <= k <= m（只会求价值的最大值）
2、体积恰好j，
当求价值的最小值：f[0][0] = 0, 其余是INF
当求价值的最大值：f[0][0] = 0, 其余是-INF
3、体积至少j，f[0][0] = 0，其余是INF（只会求价值的最小值）

一维情况
1、体积至多j，f[i] = 0, 0 <= i <= m（只会求价值的最大值）
2、体积恰好j，
当求价值的最小值：f[0] = 0, 其余是INF
当求价值的最大值：f[0] = 0, 其余是-INF
3、体积至少j，f[0] = 0，其余是INF（只会求价值的最小值）

[!summary]
可以这么思考，初始化的过程就是定义状态是否合法的过程

• 体积最多为 j，则像 f[0][j] 是合法情况
• 体积恰好为 j，则像 f[0][j] 是不合法的情况，因为不放物品时体积不会恰好为一个非 0 数
• 体积最少为 j，则像 f[0][j] 是不合法情况

代码

import java.io.*;  
import java.util.*;  
import static java.lang.Math.*;  
  
public class Main {  
  
    static int status;  
    static BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));  
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));  
    static PrintWriter cout = new PrintWriter(bw);  
    static StreamTokenizer st = new StreamTokenizer(buf);  
  
    public static int nextInt() throws IOException {  
        status = st.nextToken();  
        return (int) st.nval;  
    }  
  
    public static long nextLong() throws IOException {  
        status = st.nextToken();  
        return (long) st.nval;  
    }  
  
    public static String nextString() throws IOException {  
        status = st.nextToken();  
        return st.sval;  
    }  
  
    static int n, v, m;  
    static int[][] f;  
    static int[] a,b,c;  
    static final int INF = Integer.MAX_VALUE-666666;  
  
    public static void main(String[] args) throws IOException {  
        v = nextInt();  
        m = nextInt();  
        n = nextInt();  
        a = new int[n + 1];  
        b = new int[n + 1];  
        c = new int[n + 1];  
        f = new int[v+1][m+1];  
  
        for(int i=1;i<=n;i++){  
            a[i] = nextInt();  
            b[i] = nextInt();  
            c[i] = nextInt();  
        }  
  
        for(int i=0;i<=v;i++)  
            for(int j=0;j<=m;j++)  
                f[i][j]=INF;  
        f[0][0]=0;  
  
        for(int i=1;i<=n;i++)  
            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-a[i])][max(0,k-b[i])]+c[i]);  
  
        cout.println(f[v][m]);  
        cout.flush();  
    } // End of main  
}