算法：背包问题处理

0/1背包问题理解[1]

思路分享

有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。

定义一个二维数组 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。

第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。

综上，0-1 背包的状态转移方程为：

代码实现

public int knapsack(int W, int N, int[] weights, int[] values) {
    int[][] dp = new int[N + 1][W + 1];
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = 1; j <= W; j++) {
            if (j >= w) {
                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[N][W];
}

0/1背包问题理解[2]

作者：小小沸沸要加油
链接：https://www.nowcoder.com/discuss/3574
来源：牛客网

问题描述

　　现有n件物品和一个容量为c的背包。第i件物品的重量是重量为w[i]，价值是v[i]。已知对于一件物品必须选择取（用1表示）或者不取（用0表示），且每件物品只能被取一次（这就是“0-1”的含义）。求放置哪些物品进背包，可使这些物品的重量总和不超过背包容量，且价值总和最大。

解题思路

　　假设有5件物品，其重量分别是w={2，2，6，5，4}，价值分别是v={6，3，5，4，6}，背包容量为10。在数学问题中这是典型的线性规划问题，我们可以在线性约束范围内求解目标表达式。但是怎么用计算机语言实现呢？我们可以先这样考虑，当背包容量为1时，如何放置物品才能使背包中价值最大；同样当背包容量为2时，如何放置能使背包中价值最大，以此类推，直到背包容量为10。此时我们需要维护一张二维表m[i][j]，其中横坐标i表示物品，纵坐标表示背包容量（1<=j<=10）。

　　m[i][j]表示当可以放入前i件物品且背包容量为j时的最大价值。当只能放入第一件物品即i=0时：若背包容量j<w[0]，物品不能够被放入背包；若j>=w[0]时，物品可以放入背包，此时m[0][j]=v[0]。当可以放入前2件物品即i=1时，我们需要进行这样的处理：若j<w[1]时，说明第2件物品不能被放入背包内，此时背包的最大价值为背包中只放入第一件物品的最大价值，即m[1][j]=m[0][j]；若j>=w[1]时，假设此时背包容量j=8，第二件物品可以被放入背包内，那么便会出现两种情况：

（1）将第二件物品放入背包，那么背包中物品的最大价值是多少呢？因为第二件物品重量为w[1]=2，在将第二件物品放入背包之前，背包的容量应为j-w[1]=8-2=6，此时背包的最大价值是m[0][6]，因此若将第二件物品放入背包，其背包的最大价值m[1][j]=m[0][j-w[1]]+v[1]；

（2）不将第二件物品放入背包，那么此时背包中物品的最大价值依然为只放入第一件物品时背包的最大价值，即m[1][j]=m[0][j]；

我们选取（1）（2）中价值的较大者作为i=1，j=8时背包中的最大价值。

i=2，3，4时的分析同上，直到背包的容量为10，此时m[4][10]即为背包中物品的最大价值。

有了上面的分析，我们很容易写出下面的递归关系：

（1）i=0 当j<w[0]时，m[0][j]=0；当j>=w[0]时，m[0][j]=v[0]。

（2）i>0 当j<w[i]，m[i][j]=m[i-1][j]；当j>=w[i]，m[i][j]=max{m[i-1][j-w[i]]+v[i]，m[i-1][j]}。

得到了满足约束条件的背包中物品的最大价值后，需要知道是哪些物品被放入了背包。观察二维表m[i][j]，我们注意到m[i][c]表示当背包重量为题目中要求的c时背包的最大价值，那么在得到m[i][c]之前，我们必然是比较了m[i-1][j-w[i]]+v[i]与m[i-1][j]的大小，从而决定是否将物品放入背包。所以我们可以利用回溯的方法，若m[i][j]=m[i-1][j]，那么物品没有放入背包；否则物品一定被放入背包。因此我们可以从最后一件物品开始，一步一步回退到第一件物品，直到找到所有的物品放入背包的情况。本题中物品的装入情况如表中红色和蓝色部分所示，其中红色表示当前物品被装入背包，蓝色表示没有装入背包。

代码实现

　首先我们要说明的是，物品已经按照重量递增、价值递减的方式进行排序！

package com.company.backpack;

public class bp_01 {
    public static void main(String[] args)
    {
        int []w={2,2,6,5,4}; //物品重量
        int []v={6,3,5,4,6}; //物品价值
        int c=10;            //背包容量
        int []x=new int[5];  //物品装入情况，1表示装入，0表示不装入
        x[0]=1;
        int [][]m=new int[5][c+1];//需要维护的二维表，为了方便计算加入一列，其中第0列表示背包容量为0时背包的最大价值为0
       
        for(int i=1;i<5;i++)
        {
            for(int j=1;j<=c;j++)
            {
                if(j<w[i]) m[i][j]=m[i-1][j];
                else
                {
                    if(m[i-1][j-w[i]]+v[i]>m[i-1][j]) m[i][j]=m[i-1][j-w[i]]+v[i];
                    else m[i][j]=m[i-1][j];
                }
            }
        }
        System.out.println("背包的最大价值为"+m[w.length-1][c]);
        for(int i=4;i>=1;i--){
            if(m[i][c]>m[i-1][c]){
                x[i]=1; //装入背包
                c-=w[i]; //物品i装入背包之前背包的容量
            }
            else x[i]=0; //没有装入背包
        }
        System.out.print("装入背包的物品编号是：");
        for(int i=0;i<5;i++){
            if(x[i]==1) System.out.printf("%2d",(i+1));
        }
    }
}