目录

最优装配

目录

最优装配

给出 n 个物体,重量分别为 wi,使总重量不超过容量 C 的情况下选择尽量多的物体。 根据题目要求可以对重量进行排序然后贪心选择就好, 我们使用动态规划来解决,由于比较简单,直接给出状态方程和代码试下 $ f(i,j)= min \begin{cases} f(i-1,j-w[i]) + 1 & if\ w[i] \le j\\
f(i-1,j) otherwise \end{cases} $

 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];
    }