无界背包中的状态及状态方程已经不适用于01背包问题,那么我们来比较这两个问题的不同之处,无界背包问题中同一物品可以使用多次,而01背包问题中一个背包仅可使用一次,区别就在这里。我们将 K(ω)改为 K(i,ω) 即可,新的状态表示前 i 件物品放入一个容量为 ω的背包可以获得的最大价值。

现在从以上状态定义出发寻找相应的状态转移方程。K(i−1,ω)为 K(i,ω)的子问题,如果不放第 i 件物品,那么问题即转化为「前 i−1 件物品放入容量为 ω 的背包」,此时背包内获得的总价值为 K(i−1,ω);如果放入第 i 件物品,那么问题即转化为「前 i−1 件物品放入容量为 ω−ωi 的背包」,此时背包内获得的总价值为 K(i−1,ω−ωi)+vi. 新的状态转移方程用数学语言来表述即为:K(i,ω)=max{K(i−1,ω),K(i−1,ω−ωi)+vi}

这里的分析是以容量递推的,但是在容量特别大时,我们可能需要以价值作为转移方程。定义状态dp[i + 1][j]为前i个物品中挑选出价值总和为j 时总重量的最小值(所以对于不满足条件的索引应该用充分大的值而不是最大值替代,防止溢出)。相应的转移方程为:前i - 1 个物品价值为j, 要么为j - v[i](选中第i个物品). 即dp[i + 1][j] = min{dp[i][j], dp[i][j - v[i]] + w[i]}. 最终返回结果为dp[n][j] ≤ W 中最大的 j.

以上我们只是求得了最终的最大获利,假如还需要输出选择了哪些项如何破?

以普通的01背包为例,如果某元素被选中,那么其必然满足w[i] > j且大于之前的dp[i][j], 这还只是充分条件,因为有可能被后面的元素代替。保险起见,我们需要跟踪所有可能满足条件的项,然后反向计算有可能满足条件的元素,有可能最终输出不止一项。

import java.util.*; 
 
public class Backpack { 
    // 01 backpack with small datasets(O(nW), W is small) 
    public static int backpack(int W, int[] w, int[] v, boolean[] itemTake) { 
        int N = w.length; 
        int[][] dp = new int[N + 1][W + 1]; 
        boolean[][] matrix = new boolean[N + 1][W + 1]; 
        for (int i = 0; i < N; i++) { 
            for (int j = 0; j <= W; j++) { 
                if (w[i] > j) { 
                    // backpack cannot hold w[i] 
                    dp[i + 1][j] = dp[i][j]; 
                } else { 
                    dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - w[i]] + v[i]); 
                    // pick item i and get value j 
                    matrix[i][j] = (dp[i][j - w[i]] + v[i] > dp[i][j]); 
                } 
            } 
        } 
 
        // determine which items to take 
        for (int i = N - 1, j = W; i >= 0; i--) { 
            if (matrix[i][j]) { 
                itemTake[i] = true; 
                j -= w[i]; 
            } else { 
                itemTake[i] = false; 
            } 
        } 
 
        return dp[N][W]; 
    } 
 
    // 01 backpack with big datasets(O(n\sigma{v}), W is very big) 
    public static int backpack2(int W, int[] w, int[] v) { 
        int N = w.length; 
        // sum of value array 
        int V = 0; 
        for (int i : v) { 
            V += i; 
        } 
        // initialize 
        int[][] dp = new int[N + 1][V + 1]; 
        for (int[] i : dp) { 
            // should avoid overflow for dp[i][j - v[i]] + w[i] 
            Arrays.fill(i, Integer.MAX_VALUE >> 1); 
        } 
        dp[0][0] = 0; 
        for (int i = 0; i < N; i++) { 
            for (int j = 0; j <= V; j++) { 
                if (v[i] > j) { 
                    // value[i] > j 
                    dp[i + 1][j] = dp[i][j]; 
                } else { 
                    // should avoid overflow for dp[i][j - v[i]] + w[i] 
                    dp[i + 1][j] = Math.min(dp[i][j], dp[i][j - v[i]] + w[i]); 
                } 
            } 
        } 
 
        // search for the largest i dp[N][i] <= W 
        for (int i = V; i >= 0; i--) { 
            // if (dp[N][i] <= W) return i; 
            if (dp[N][i] <= W) return i; 
        } 
        return 0; 
    } 
 
    // repeated backpack 
    public static int backpack3(int W, int[] w, int[] v) { 
        int N = w.length; 
        int[][] dp = new int[N + 1][W + 1]; 
        for (int i = 0; i < N; i++) { 
            for (int j = 0; j <= W; j++) { 
                if (w[i] > j) { 
                    // backpack cannot hold w[i] 
                    dp[i + 1][j] = dp[i][j]; 
                } else { 
                    dp[i + 1][j] = Math.max(dp[i][j], dp[i + 1][j - w[i]] + v[i]); 
                } 
            } 
        } 
 
        return dp[N][W]; 
    } 
 
    public static void main(String[] args) { 
        int[] w1 = new int[]{2, 1, 3, 2}; 
        int[] v1 = new int[]{3, 2, 4, 2}; 
        int W1 = 5; 
        boolean[] itemTake = new boolean[w1.length + 1]; 
        System.out.println("Testcase for 01 backpack."); 
        int bp1 = backpack(W1, w1, v1, itemTake); // bp1 should be 7 
        System.out.println("Maximum value: " + bp1); 
        for (int i = 0; i < itemTake.length; i++) { 
            if (itemTake[i]) { 
                System.out.println("item " + i + ", weight " + w1[i] + ", value " + v1[i]); 
            } 
        } 
 
        System.out.println("Testcase for 01 backpack with large W."); 
        int bp2 = backpack2(W1, w1, v1); // bp2 should be 7 
        System.out.println("Maximum value: " + bp2); 
 
        int[] w3 = new int[]{3, 4, 2}; 
        int[] v3 = new int[]{4, 5, 3}; 
        int W3 = 7; 
        System.out.println("Testcase for repeated backpack."); 
        int bp3 = backpack3(W3, w3, v3); // bp3 should be 10 
        System.out.println("Maximum value: " + bp3); 
    } 
}

发布评论
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

Greatest Common Divisor讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。