算法-0/1背包问题

古城微笑少年丶 2024-04-18 10:34 48阅读 0赞

## 1. 求最大价值 ##

给定 背包的容积 W，物品的体积数组 weights 和价值数组 values, 求背包能装入物品的最大价值。  
例如：  
W=6  
weights = \{1, 2, 3, 4\};  
values = \{2, 4, 3, 6\};  
输出最大价值 ：10

## 2. 解法 ##

动态规划法， 0-1 Knapsack.一个物品只能用一次。

*  定义一个二维数组 dp 存储最大价值，其中 dp\[i\]\[j\] 表示背包装入前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w，价值为 v，
 *  根据第 i 件物品是否添加到背包中，可以分两种情况讨论：
    
     *  第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，dp\[i\]\[j\] = dp\[i-1\]\[j\]。
     *  第 i 件物品添加到背包中，dp\[i\]\[j\] = dp\[i-1\]\[j-w\] + v

则递推式为 `dp[i][j] = max(dp[i-1][j-w] + v,dp[i-1][j])` ，可以看到不管第 i 件物品有没有加到背包中，最大价值都和 i-1 相关，则变量 i 对于最大价值的影响可消去，优化为一维数组递推式：

*  `dp[j] = max(dp[j-w] + v,dp[j])`

每个物品加入后遍历更新数组
    dp[0]:0 dp[1]:2 dp[2]:2 dp[3]:2 dp[4]:2 dp[5]:2 dp[6]:2 
    dp[0]:0 dp[1]:2 dp[2]:4 dp[3]:6 dp[4]:6 dp[5]:6 dp[6]:6 
    dp[0]:0 dp[1]:2 dp[2]:4 dp[3]:6 dp[4]:6 dp[5]:7 dp[6]:9 
    dp[0]:0 dp[1]:2 dp[2]:4 dp[3]:6 dp[4]:6 dp[5]:8 dp[6]:10

/**
         * @param W       背包最大体积容量
         * @param weights 物品体积数组 {1,2,3,4}
         * @param values  物品价值数组 {2,4,3,6}
         * @return 返回最大价值
         **/
        public int knapsack(int W, int[] weights, int[] values) {
        
            int length = weights.length;
            /*int[][] dp = new int[length + 1][W + 1];
            for (int i = 1; i <= length; i++) { // 物品数组循环
                int w = weights[i - 1];
                int v = values[i - 1];
                for (int j = 1; j <= W; j++) { // 物品体积循环
                    if (j >= w) { // 第 i 个物品加入背包
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            return dp[length][W];*/
    
            int[] dp = new int[W + 1]; // 一维数组优化
            for (int i = 1; i <= length; i++) {
         // 物品数组循环
                int w = weights[i - 1];
                int v = values[i - 1];
                for (int j = W; j >= 1; j--) {
         // 0-1 背包问题一维数组表示需逆序遍历,否则之前的计算
                                              //结果会对之后的结果造成影响
                    if (j >= w) {
        
                        dp[j] = Math.max(dp[j], dp[j - w] + v);
                        System.out.println("dp["+j+"]:"+dp[j]+" dp["+(j - w)+"]:"+dp[j - w]);
                    }
                }
            }
            return dp[W];
        }