算法-0/1背包问题
标签:算法

0/1背包问题

有一个背包,它的容量为C (Capacity),现在有n种不同的物品,编号为0...n-1,其中每一件物品的重量为w(i),价值为v(i)。问可以向这个背包中盛放哪些物品,使得在不超过背包容量的基础上,物品的总价值最大

如果直接用暴力解法的话,那么为 O((2^n)*n),即每件物品都有放入和不放入的两种情况,一共有n个,那么就有 2^n,那么n个的总的情况为O((2^n)*n)

0/1背包问题不能用贪心解法,因为它只能将物品放入和不放入的两种情况。

比如下面这种情况

id 0 1 2
weight 1 2 3
value 6 10 12
v/w 6 5 4

可见如果我们使用贪心策略,假设背包的大小为5的话,那么选择的是0和1,此时的最大value为16,而我们选择1和2的话,那么value将是22。

状态转移

F(n,C)考虑将n个物品放进容量为C的背包,使得价值最大

F(i,C)=F(i-1,c)

​ =v(i)+F(i-1,c-w(i))

可见对于n个物品,我们有两个策略,选择放入和不放入,我们应该选择它们的最大值

F(i,c)=max(F(i-1,c) , v(i)+F(i-1,c-w(i)))

动态规划策略

自顶向下,记忆化搜索

    /**
     *自顶向下,记忆化搜索
     */
    static class Solution1{
         int[][] memo;
         /**
          * 0-1背包
          * @param w 物品重量的数组
          * @param v 物品价值的数组
          * @param C 背包最大的容量
          * @return 最后能装下的最大价值
          */
        public int knapsack01(int[] w,int[] v,int C){
            int n=w.length;
//            横坐标为个数,纵坐标为容量
            memo=new int[n+1][C+1];
            for (int i = 0; i < memo.length; i++) {
                Arrays.fill(memo[i],-1);
            }
            return bestValue(w,v,n-1,C);
        }

         private int bestValue(int[] w, int[] v, int index, int c) {
            if (index <0 || c<=0){
                return 0;
            }
            if (memo[index][c]!=-1){
                return memo[index][c];
            }
//            不放入的情况
            int res=bestValue(w,v,index-1,c);
            if (c>=w[index]){
//                和放入的情况取最大值
                res=Math.max(res,v[index]+bestValue(w,v,index-1,c-w[index]));
            }
            memo[index][c]=res;
            return res;
         }
     }

我们使用memo数组来解决重叠子问题,由于这里存在两个约束条件,故我们需要 开辟一个二维数组来解决。

动态规划,自底向上

 /**
     * 动态规划
     */
    static class Solution2{
         public int knapsack01(int[] w,int[] v,int C){
             int n=w.length;
             if (n==0 || C==0){
                 return 0;
             }
             int[][] memo= new int[n+1][C+1];
//             处理第0行的情况
             for (int j = 0; j <= C; j++) {
                 memo[0][j]=(j>=w[0]?v[0]:0);
             }
//             从第一行处理
             for (int i = 1; i < n; i++) {
                 for (int j = 0; j <=C; j++) {
//                     不考虑第i个物品的情况
                     memo[i][j]=memo[i-1][j];
//                     当容量大于w[i]时才可以放入
                     if (j>=w[i]){
                         memo[i][j]=Math.max(memo[i][j],v[i]+memo[i-1][j-w[i]]);
                     }
                 }
             }
             return memo[n-1][C];
         }
     }

动态规划,空间优化,使用两行

由于第i行的元素只依赖于第i-1行元素,理论上,只需要保持两行元素,空间复杂度:O(2*C)=O(C)

即我们可以只用两行,上面一行处理i为偶数的结果,下面一行处理i为奇数的结果

/**
     * 动态规划优化版,只用两行
     */
    static class Solution3{
        public int knapsack01(int[] w,int[] v,int C){
            int n=w.length;
            if (n==0|| C==0){
                return 0;
            }
            int[][] memo= new int[2][C+1];
            for (int j = 0; j <= C; j++) {
                memo[0][j]=(j>=w[0]?v[0]:0);
            }
            for (int i = 1; i < n; i++) {
                for (int j = 0; j <=C; j++) {
                    memo[i%2][j]=memo[(i-1)%2][j];
                    if (j>=w[i]){
                        memo[i%2][j]=Math.max(memo[i%2][j],v[i]+memo[(i-1)%2][j-w[i]]);
                    }
                }
            }
            return memo[(n-1)%2][C];
        }
    }

故只要涉及到memo的行号的时候,我们都需要与2进行取余计算。这样我们使得我们可以使的我们现在处理 的背包容量比原来要大很多。

动态规划,空间优化,使用一行

由于我们考虑的位置是当前位置和之前的c-w(i)的位置,故我们可以从后向前推进。

    /**
     * 动态规划优化版,只用一行
     */
    static class Solution4{
        public int knapsack01(int[] w,int[] v,int C){
            int n=w.length;
            if (n==0|| C==0){
                return 0;
            }
            int[] memo= new int[C+1];
            for (int j = 0; j <= C; j++) {
                memo[j]=(j>=w[0]?v[0]:0);
            }
            for (int i = 1; i < n; i++) {
                for (int j = C; j >=w[i]; j--) {
                    memo[j]=Math.max(memo[j],v[i]+memo[j-w[i]]);
                }
            }
            return memo[C];
        }
    }
  • 5 min read

CONTRIBUTORS


  • 5 min read