1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

    public static int getMaxNumbers(int n, int c, int[] w) {
        // 使用一维数组保存最优解
        int[] f = new int[c + 1];
        // 初始化
        for (int i = 0; i < n + 1; i++) {
            f[0] = 0;
        }

        for (int i = 1; i < n + 1; i++) {
            // 需要倒序，防止被覆盖
            for (int j = c; j >= 0; j--) {
                if (w[i] <= j) {
                    f[j] = Math.max(f[j], f[j - w[i]] + 1);
                }
            }
        }
        return f[c];
    }