01背包

当时没想到可以把价值当作体积，直接用的boolean来代表当前是否可以达到。

时间复杂度 O(nV)

Java 代码

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int V = in.nextInt(), n = in.nextInt();
        boolean[] dp = new boolean[V + 1];
        dp[0] = true;
        for (int i = 0; i < n; ++i) {
            int v = in.nextInt();
            for (int j = V; j >= 0; --j) {
                if (j >= v) dp[j] |= dp[j - v];
                if (i == n - 1 && dp[j]) {
                    System.out.println(V - j);
                    break;
                }
            }
        }
        in.close();
    }
}