首页 > 代码库 > 如何理解背包问题

如何理解背包问题

  1. 问题

    假定背包的最大容量为W,N件物品,每件物品都有自己的价值和重量,将物品放入背包中使得背包内物品的总价值最大。

    技术分享
  2.  

    背包问题wiki

    可以想象这样一个场景——小偷在屋子里偷东西,他带着一只背包。屋子里物品数量有限——每件物品都具有一定的重量和价值——珠宝重量轻但价值高,桌 子重但价值低。最重要的是小偷背包容量有限。很明显,他不能把桌子分成两份或者带走珠宝的3/4。对于一件物品他只能选择带走或者不带走。

    示例:

     

     

     

    Knapsack Max weight : W = 10 (units)

    Total items                  : N = 4

    Values of items           : v[] = {10, 40, 30, 50}

    Weight of items          : w[] = {5, 4, 6, 3}

     

     

     

     

    从示例数据大致估算一下,最大重量为10时背包能容纳的物品最大价值为50+40=90,重量为7。

  3.  

    解决方法:

    最佳的解决方法是使用动态规划——先得到该问题的局部解然后扩展到全局问题解。

    构建物品X在不同重量时的价值数组V(Value数组):

     

     

     

    V[N][W] = 4 rows * 10 columns

     

     

     

     

    该矩阵中的每个值的求解都代表一个更小的背包问题。

    初始情况一:对于第0列,它的含义是背包的容量为0。此时物品的价值呢?没有。因此,第一列都填入0。

    初始情况二:对于第0行,它的含义是屋内没有物品。那么没有任何物品的背包里的价值多少呢?还是没有!所有都是0。

    技术分享
  4.  

    步骤:

    1、现在,开始填入数组每一行的值。第1行第1列代表什么含义呢?对于第一个物品,可以把重量为1的该物品放入背包吗?不行。第一个物品的重量是5。因此,填入0。实际上直到第5列(重量5)之前都应该填入0。2、对于第1行的第5列(重量5),意味着将物品1放入背包。填入10(注意,这是Value数组):

    技术分享
  5.  

    3、继续,对于第6列,我们可以再放入重量为1(重量值-物品的重量)的物品吗。我们现在只考虑物品1。由于我们加入物品1之后就不能再加入额外的重量,可以很直观地看到其余的列都应该还是相同的值。

    技术分享
  6.  

    4、接着,有意思的事情就要出现了。在第3行第4列,此时重量为4。

    需要作以下判断:

    1.可以放入物品2吗——可以。物品2的重量为4。

    2.不加入物品2的话当前已有物品的重量的Value值是否更大——查看相同重量时的前一行的值。不是。前一行的值为0,重量4时不能放入物品1。

    3.在这个重量时可以放入两件物品使得价值最大吗?——不能。此时重量减去物品2的重量后为0。

    技术分享
  7.  

    为什么是前一行?

    简单来说,重量为4的前一行的值本身就是个更小的背包问题解,它的含义是到该重量时背包内物品的最大价值(通过遍历物品得到)。

    举个例子:

    当前物品价值 = 40

    当前物品重量 = 4

    剩余重量 = 4-4 = 0

    查看上面的行(物品1或者其余行的值)。剩余容量为0时,可以再容纳物品1吗?对于该给定的重量值上面的行还有任何值吗?

    计算过程如下:

    1) 计算不放入该物品时该重量的最大价值:

     

     

     

    previous row, same weight = 0

    => V[item-1][weight]

     

     

     

     

    2) 计算当前物品的价值 + 可以容纳的剩余重量的价值

     

     

     

    Value of current item

    + value in previous row with weight 4 (total weight until now (4) - weight of the current item (4))

     => val[item-1] + V[item-1][weight-wt[item-1]]

     

     

     

     

    找到二者之中的最大值40(0和40)。

    3) 下一次最重要的位置为第2行第9列。意味着此时重量为9,放入两件物品。根据示例数据现在可以放入两件物品。我们作了以下判断:

     

    1. The value of the current item = 40

    2. The weight of the current item = 4

    3. The weight that is left over = 9 - 4 = 5

    4. Check the row above.  At the remaining weight 5, are we able to

    技术分享
  8.  

    计算如下:

    不加入该物品时该重量的最大价值:

     

     

    previous row, same weight = 10

    计算当前物品的价值+可以容纳的剩余重量的价值

     

    Value of current item (40)

    + value in previous row with weight 5 (total weight until now (9) - weight of the current item (4))

     = 10

    10vs50 = 50。

    解决了所有的子问题之后,返回V[N][W]的值——4件物品重量为10时:

     

     

     

     

    技术分享
  9.  

    复杂度

    解法的复杂度非常直观。在N次循环中有W次循环 => O(NW)

  10.  

    实现

    Java代码实现:

    class Knapsack {

        public static void main(String[] args) throws Exception {

            int val[] = {10, 40, 30, 50};

            int wt[] = {5, 4, 6, 3};

            int W = 10;

     

            System.out.println(knapsack(val, wt, W));

        }

     

        public static int knapsack(int val[], int wt[], int W) {

            //Get the total number of items.

            //Could be wt.length or val.length. Doesn‘t matter

            int N = wt.length;

     

            //Create a matrix.

            //Items are in rows and weight at in columns +1 on each side

            int[][] V = new int[N + 1][W + 1];

     

            //What if the knapsack‘s capacity is 0 - Set

            //all columns at row 0 to be 0

            for (int col = 0; col <= W; col++) {

                V[0]<div class="column col-1-2"><p></p></div> = 0;

            }

     

            //What if there are no items at home. 

            //Fill the first row with 0

            for (int row = 0; row <= N; row++) {

                V[row][0] = 0;

            }

     

            for (int item=1;item<=N;item++){

                //Let‘s fill the values row by row

                for (int weight=1;weight<=W;weight++){

                    //Is the current items weight less

                    //than or equal to running weight

                    if (wt[item-1]<=weight){

                        //Given a weight, check if the value of the current

                        //item + value of the item that we could afford

                        //with the remaining weight is greater than the value

                        //without the current item itself

                        V[item][weight]=Math.max (val[item-1]+V[item-1][weight-wt[item-1]], V[item-1][weight]);

                    }

                    else {

                        //If the current item‘s weight is more than the

                        //running weight, just carry forward the value

                        //without the current item

                        V[item][weight]=V[item-1][weight];

                    }

                }

     

            }

     

            //Printing the matrix

            for (int[] rows : V) {

                for (int col : rows) {

                    System.out.format("%5d", col);

                }

                System.out.println();

            }

     

            return V[N][W];

        }

    }

如何理解背包问题