动态规划[4]-01背包问题

2018/03/15 刷题 动态规划 01背包问题
  本文为「原创」内容,如需转载请注明出处!             
本文共 3058 字,需 38 分钟阅读

问题

在N件物品取出若干件放在容量为w的背包里,每件物品的体积为w1,w2,…,wn(wi为整数),与之相对应的价值为p1,p2,…pn(pi为整数)。求背包能够容纳的最大价值。

注:每件物品只有一个,要么取要么不取

思路

  1. 这是一个有约束条件的求最优解的类型,考虑使用动态规划。
  2. 状态描述:
     V(i,j) 表示当容量为 j, 放入了 i 个商品的最大总价值
     p(i) 表示第 i 个商品的 价值
     w(i) 表示第 i 个商品的 重量
    
  3. 状态转移: \(V(i,j) = \begin{cases} 0 & i=0 或者 j=0 \\ max \begin{cases} V(i-1,j) & j < w(i) \\ V(i-1,j-w(i)) + p(i) & j \geq w(i) \\ \end{cases} \end{cases}\)
     注:
        很明显当 i=0 或者 j=0 的时候没有物品被放入背包,所以价值为 0
        当 j < w(i) 表示当前容量不能放下 i,所以价值仍为 V(i-1,j)
        当 j >= w(i) 的时候,这是就要比较放入 i 和不放 i 谁的价值更高
         V(i-1,j-w(i)) + p(i) 表示放入 i
         其中V(i-1,j-w(i)) 表示放入 i 之前的最高价值
    
    
  4. 一个很关键的点,所有数据都是整数,所以 j 只能取整数,所求为 V(i,capacity)

实现

/**
 * 经典的0/1背包问题
 *
 * @author ychost
 * @date 2018-3-15
 */
public class Knapsack {
    /**
     * 获取背包的所装商品的总价值
     *
     * @param goods 商品对象,[i][0] 表示第 i 商品的重量, [i][1] 表示第 i 个商品的价值
     * @param w     背包的总重量限制
     * @return 背包所装商品的最大价值
     */
    static int getMaxPrice(int[][] goods, int w) {
        int[][] dp = new int[goods.length + 1][w + 1];
        for (int j = 0; j <= w; j++) {
            for (int i = 1; i <= goods.length; i++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                } else {
                    //背包的容量不能放下该商品
                    if (j < goods[i - 1][0]) {
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        int weight = goods[i - 1][0];
                        int price = goods[i - 1][1];
                        //对比放下该商品和不放该商品总价值的大小
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight] + price);
                    }
                }
            }
        }
        print(dp, goods, w);
        return dp[goods.length][w];
    }

    /**
     * 打印出商品的取舍情况,0 表示舍弃,1 表示取
     *
     * @param dp    动态规划结果
     * @param goods 商品对象
     * @param w     背包总重量
     */
    static void print(int[][] dp, int[][] goods, int w) {
        int j = w;
        int i = goods.length;
        Stack<Integer> stack = new Stack<>();
        while (j > 0 && i > 0) {
            int weight = goods[i - 1][0];
            int price = goods[i - 1][1];
            //容量不足,所以该商品没有被放入,上一次的容量为 --j
            if (j < weight) {
                stack.push(0);
                --i;
                --j;
            } else {
                //没有放入该商品,上一次的容量还是 j
                if (dp[i][j] == dp[i - 1][j]) {
                    stack.push(0);
                    --i;
                    //该商品被放入了,则上一次的容量为 j-weight
                } else if (dp[i][j] == dp[i - 1][j - weight] + price) {
                    stack.push(1);
                    --i;
                    j -= weight;
                } else {
                    throw new RuntimeException("dp 有误");
                }
            }
        }
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

测试数据

int[] weights = {70, 73, 77, 80, 82, 87, 90, 94, 98, 106, 110, 113, 115, 118, 120};
int[] prices = {135, 139, 149, 150, 156, 163, 173, 184, 192, 201, 210, 214, 221, 229, 240};
int w = 750;
// output
// 1458

搜索

    文章目录