01背包问题

背包问题

背包问题主要包含以下3种基本的问题：

• 01背包
• 完全背包
• 多重背包

其中对于每一种xx背包问题还存在一个特殊的情形，即要求背包恰好被装满，这种特殊问题的求解主要是在动态规划的状态数组的初始化做一下特殊的处理。

除此之外，有时候我们不仅仅要求背包能装下的最大物品的价值，我们还希望得到具体的装包方案，这里就会涉及到状态数组的回溯（Track），下面会举例说明。

问题描述

01背包问题是背包问题中最简单最基础的一类问题，问题描述如下：

给定n$n$件物品，对于第i$i$件物品，其价值为vi$v_i$，重量为wi$w_i$，与此同时还存在一个体积为V$V$的背包，每件物品只有一件，因此每件物品可以选择是否放进背包，求背包能装下的物品的最大价值P$P$。

对于该问题，对应的数学模型是一个简单的01规划问题：

对应的模型为：

s.t.  ∑ni=1 wi∗xi<=V,xi=0,1$s.t.\sum _{i=1}^n{w}_i\ast x_i<=V,x_i=0,1$

maxP=∑ni=1vi∗xi$maxP=\sum _{i=1}^n{v}_i\ast x_i$

解法

01背包问题常常采用动态规划的方法去求解，状态转移方程为：

{fi,j=fi−1,jif wi>jfi,j=max(fi−1,j,fi−1,j−wi+vi) if wi<=j$$\{\begin{array}{rcl}& & f_{i,j}=f_{i-1,j}if{w}_i>j\\ & & f_{i,j}=max(f_{i-1,j},f_{i-1,j-w_i}+v_i)if{w}_i<=j\end{array}$$

fi,j$f_{i,j}$表示前i$i$种物品装进容量为j$j$的背包里面获取的最大价值，因此对于第i$i$件物品来放进大小为j$j$的背包来讲：

• 如果wi>j$w_i>j$，那么该物品放不进去，则此时的收益和前i−1$i-1$件物品放进大小为j$j$的背包的最大收益一样，即fi,j=fi−1,j$f_{i,j}=f_{i-1,j}$；
• 若果wi<=j$w_i<=j$， 则该物品可以放进去，但是此时是有两种选择的，即放进去或者不放进去，因此需要评估两种选择的收益大小：
  
  • 将第i$i$件物品不放进去：收益为fi−1,j$f_{i-1,j}$
  • 将第i$i$件物品放进去，那么此时前一个状态只可能是：前i−1$i-1$件物品放进大小为j−wi$j-w_i$的背包中。因此将第i$i$件物品放入背包的收益是fi−1,j−wi+vi$f_{i-1,j-w_i}+v_i$
  • 最后两个选择中最大的便是当前的收益

代码如下：

public static int knapsackProblemZeroOne(int[] value, int[] weight, int bagV) {
        int[][] dp = new int[value.length][bagV + 1]; 
        // dp[i][j] 表示前i个物品，装填大小为j的背包所能达到的最大价值;
        // 显然因为value[0] = 0,dp[0][0~bagV] = 0 ;
        for (int i = 1; i < value.length; i++) {
            for (int j = 1; j <= bagV; j++) {
                if (weight[i] > j) {// 第i个物品放不进去
                    dp[i][j] = dp[i - 1][j];
                } else {// 第i个物品能放进去
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                }
            }
        }
        return dp[value.length - 1][bagV];
    }

上述代码里面的两层for循环，由于是从1开始的，因此对于对于参数value，里面的有效数据应该也是从1开始计数的，因此在value数组和weight数组的第一个元素都应该置为0。

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] value = new int[] { 0, 1, 4, 3,6};// 物品的价值
        int[] weight = new int[] { 0, 5, 2, 4, 3};// 物品的重量
        int bagV = 15;// 背包的大小
        System.out.println(knapsackProblemZeroOne(value, weight, bagV));
    }

实现细节：

• value和weight数组的第一个元素应该都为0，以便后续处理可以从1开始计数；
• dp状态数组的列下标也是从1开始计数的，因此申请空间的时候应该是dp[n][bagV+1];

dp数组的求解正如如下表格一样，从左上到右下依次求解：

空间优化

上述算法的时间复杂度为O(NV)$O(NV)$，其中N$N$为物品的数量，V$V$为背包的体积。
但是通过上述的状态转移方程我们发现，其实fi,j$f_{i,j}$的值仅仅和fi−1,j$f_{i-1,j}$， fi−1,j−wi$f_{i-1,j-w_i}$有关，也就是说第i$i$件物品只和前一件物品有关（dp二维数组的第i行可以通过第i-1行推出来），因此我们可以将二维数组改写为一维数组，俗称滚动数组。

    public static int knapsackProblemZeroOneOptimization(int[] value, int[] weight, int bagV) {

        int[] dp = new int[bagV + 1]; // dp[i][j] 表示前i个物品，装填大小为j的背包所能达到的最大价值
        // 显然，dp[0][0~bagV] = 0, dp[0~v.length-1][0] = 0;
        for (int i = 1; i < value.length; i++) {
            for (int j = bagV; j >= weight[i]; j--) {//从后往前更新，因为后一项状态dp[j]需要利用上一轮的j前面的状态;
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        return dp[bagV];
    }

关键要理解这里的写法：

for (int j = bagV; j >= weight[i]; j--)

经过此番优化后，时间复杂度不变，空间复杂度降为O(V)$O(V)$。

状态回溯

以上的算法只是给出能够得到的最大收益值P$P$，但是有时候我们希望得到具体的装包方案，即我们需要知道哪些物品需要装包，哪些不需要。

根据状态数组从后往前倒退，即可得到一条路径，将该路径上的信息保存便可以得到方案。

对于dp[i][j]，该值来源于两个地方:

• dp[i-1][j]
• dp[i-1][j-wi]

因此可以写出下面的代码求得装包方案：

    public static int[] tracback(int[][] dp, int[] weight, int bagV) {
        int[] res = new int[weight.length];
        int j = bagV;
        for (int i = weight.length - 1; i >= 1; i--) {//从后往前推
            if (dp[i][j] == dp[i - 1][j]) {//dp[i][j]来源于dp[i-1][j]说明第i件物品装不进去
                res[i] = 0;
            } else {
                res[i] = 1;
                j -= weight[i];
            }
        }
        res[0] = dp[0][j] > 0 ? 1 : 0;
        return res;
    }

状态回溯的求解正如如下二维表格一样，从右下往左上倒推：

references

1. http://dongxicheng.org/structure/knapsack-problems/
2. https://blog.csdn.net/fx677588/article/details/68951593
3. https://baike.baidu.com/item/0-1%E8%A7%84%E5%88%92/5790449?fr=aladdin