AcWing 1020. 潜水员 Java

学到了，确实是非常好的一道题

我的理解

我来说下我的理解：我希望有不对的地方欢迎大家指正
这里需要枚举0-m的原因是因为，之前的 至多/最多 恰好，都意味着 $j - v \ge 0, j \ge v,v \ge 0$ 。而这道题的至少表明，可能存在大于体积（限制）的物品会可能作为最后最小的价值。意味着有比需要体积大的物品仍然需要被更新。而$j - v \le 0$ 被置为0，是因为，当前选择了更大的体积（限制）。那么从剩余的物品i-1个中选择的时候，是不再需要满足当前这一维的限制（限制就是体积）了，因为选第i个物品的时候就已经够了。

代码

import java.io.*;
import java.util.*;
public class Main{
    static int N = 110,n,m,k,INF = 0xfffff;
    //二维费用的01背包问题
    static int[][] f = new int[N][N];
    static int Int(String s){return Integer.parseInt(s);}
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args)throws IOException{
        String[] arrStr = br.readLine().split(" ");
        m = Int(arrStr[0]);n = Int(arrStr[1]);
        arrStr = br.readLine().split(" ");
        k = Int(arrStr[0]);
        //记得初始化
        for(int i = 0 ;i < N ;i++) Arrays.fill(f[i],INF);
        f[0][0] = 0;
        for(int i =1;i <= k;i ++){
            arrStr = br.readLine().split(" ");
            int v1 = Int(arrStr[0]);int v2 = Int(arrStr[1]);int w = Int(arrStr[2]);

            //枚举全部
            //至少意味着，有更多体积的物品也需要被更新
            for(int j = m; j >= 0;j --){
                for(int k= n; k >= 0 ;k --){
                    //当j - v1 < 0的时候，意味着从剩下物品中选择的时候
                    //不再需要这一维的状态了
                    f[j][k] = Math.min(f[j][k],f[Math.max(0,j - v1)][Math.max(0,k - v2)] + w);
                }
            }
        }
        pw.println(f[m][n]);
        pw.flush();br.close();pw.close();
    }
}