题解 | 装箱问题

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int V = in.nextInt(), n = in.nextInt();//n and Volume
        // 这里我把价值和重量的字母正常写了，而非像题目那样有点反直觉
        int []v = new int [n]; //价值代表重量，最大价值代表最小的剩余空间     
        for (int i = 0; i < n; ++i) {            
            v[i] = in.nextInt();
        }
        //dp[i]表示在容量为i时的最大价值
        //求解问题一
        int []dp1 = new int [V + 1];
        for (int i = 0; i < n; ++i) {
            for (int j = V; j >= v[i]; --j) {
                dp1[j] = Math.max(dp1[j - v[i]] + v[i], dp1[j]);
            }
        }
        System.out.println(V-dp1[V]);
    }
}