背包问题之0-1背包算法详解-Toy模板网

这篇具有很好参考价值的文章主要介绍了背包问题之0-1背包算法详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、0-1背包问题描述

有5件物品和1个背包，背包最多只能装下8公斤的物品。怎样选择物品，使得背包能装下并且得到的价值最大。物品的重量和价值如下所示：

物品1: 6公斤　　   价值48元
物品2: 1公斤  　　价值7元
物品3: 5公斤  　　价值40元
物品4: 2公斤　　价值12元
物品5: 1公斤  　　价值8元

二、解题思路

可以先考虑装0公斤物品时背包的最大价值，再考虑装1公斤物品时背包的最大价值、装2公斤物品时背包的最大价值、装3公斤物品时背包的最大价值，以此类推。定义一个数组dp[i][j]，i 表示当前物品的序号，j表示当前背包承重，dp[i][j]表示前i个物品、背包承重为j时的最大价值。当 i 和 j 都循环到最后一个值时，dp[i][j] 就是所求的最大价值。对于这5件物品，按顺序取一件，先判断能否装下。若不能装下，则不放入，此时背包的最大价值就是装前一件物品时的最大价值。若能装下，再判断装下这件物品和不装下这件物品，哪个价值更高。逐次遍历，将背包的最大价值记录下来，进行填表，如下所示：

书包重量（公斤）	1	2	3	4	5	6	7	8
物品不存在	0	0	0	0	0	0	0	0
物品1：6公斤、48元	0	0	0	0	0	48	48	48
物品2：1公斤、7元	7	7	7	7	7	48	55	55
物品3：5公斤、40元	7	7	7	7	40	48	55	55
物品4：2公斤、12元	7	12	19	19	40	48	55	60
物品5：1公斤、8元	8	15	20	27	40	48	56	63

这个表是怎么来的呢？横着逐排填写。物品不存在时，背包最大价值肯定是0。当书包承重为0公斤时，背包最大价值肯定是0。

选择第1件物品，背包承重从1公斤到5公斤时，都装不下物品1，所以dp[1][1]到dp[1][5]都是0。直到背包承重时6公斤时，才装下第1件物品，所以dp[1][6]=48。背包承重为7、8公斤时，也只能选择物品1，所以值还是一样的。

接下来，选取第2件物品。书包承重1公斤时，只能装下物品2，此时书包最大价值是7，也就是dp[2][1] = 7。一直到书包承重5公斤时，都只能装下物品2，dp[2][1]到dp[2][5]都是等于7。书包承重6公斤时，可以装物品1或物品2，两者只能装1个，通过对比物品1和物品2的价值大小，我们选择物品1，即dp[2][6]=48。书包承重7公斤时，可以同时装物品1、物品2，此时dp[2][7]=物品2的价值 + 物品1的价值=55。dp[2][8]也是同样的道理。

可以进行抽象思考：对物品按顺序编号，物品i的重量为weight[i]，价值为value[i]。选取第i件物品时，已知背包当前最大承重为j，怎样装载物品，才能使得背包最大价值dp[i][j]最大？

1.如果物品i的重量weight[i]超过背包当前承重j，不能装下，那么就不装了。此时，背包最大价值 dp[i][j]就是选取前一件物品时背包最大价值，即dp[i][j] = dp[i-1][j]。

2.如果物品i的重量weight[i]小于背包当前承重j，那么选择是装、还是不装呢？

未选取物品i时，已选取前i-1件物品，此时背包承重为j，背包最大价值为dp[i-1][j]。

要想装下物品i，第1步：先将“当前背包承重j”腾出“物品i的重量值weight[i]”，此时背包承重为“j - weight[i]”，背包最大价值为dp[i-1][j - weight[i]]。第2步：装下物品i，背包最大价值增加“物品i的价值value[i]”，此时背包承重为j，背包最大价值为dp[i-1][j - weight[i]] + value[i]。对比不装物品i时背包最大价值和装下物品i后背包最大价值。

若不装物品i时背包价值更大，则不装物品i，此时背包最大价值就是装前一件物品时的最大价值，即dp[i][j] = dp[i-1][j] 。

若装下物品i后背包价值更大，则装下物品i，此时背包最大价值就是装下物品i后的背包最大价值，即dp[i][j] = dp[i-1][j - weight[i]] + value[i]。

由此，可以总结出状态转移方程：

当前物品i的重量weight[i]大于背包承重j时，背包最大价值为：

dp[i][j] = dp[i-1][j]

当前物品i的重量weight[i]小于等于背包承重j时，背包最大价值为：

dp[i][j] = Math.max(dp[i-1][j - weight[i]] + value[i], dp[i-1][j])

三、Java编码实现

根据上一节的状态转移方程，我们很容易就能编程实现功能。

3.1 朴素求解背包最大价值与选取物品列表

代码为：

package com.test.packalgorithm;

/**
 * 0-1 背包
 */
public class ZeroOnePackCal {

    /**
     * 获取最大价值
     *
     * @param N 物品个数
     * @param W 背包最大承重
     * @param weight 物品重量数组
     * @param value 物品价值数组
     * @return 最大价值
     */
    public int[][] getDp(int N, int W,  int[] weight, int[] value) {
        // 定义一个数组dp[i][j]  i表示当前物品的序号, j表示当前书包的重量
        int[][] dp = new int[N + 1][ W + 1];
        for (int j = 0; j <= W; j++) {  // 物品不存在时，最大价值肯定是0
            dp[0][j] = 0;
        }
        for (int i = 1; i <= N; i++) {  // 背包重量为0时，最大价值肯定是0
            dp[i][0] = 0;
        }

        for (int i = 1; i <= N; i++) {  // 从第1个物品开始选取
            for (int j = 1; j <= W; j++) {
                if (weight[i] <= j) { // 第i件物品重量 小于等于 当前承载重量，根据价值大小判断是否放入。
                    dp[i][j] = Math.max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j]);
                } else { // 第i件物品重量大于当前承载重量，则不放入。
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp;
    }

    public static void main(String[] args) {
        int N = 5; // 物品个数
        int W = 8; // 背包承载最大重量
        int[] w = new int[N + 1]; // 每件物品的重量（为方便理解，下标从1开始）
        w[1] = 6;
        w[2] = 1;
        w[3] = 5;
        w[4] = 2;
        w[5] = 1;
        int[] v = new int[N + 1]; // 每件物品的价值（为方便理解，下标从1开始）
        v[1] = 48;
        v[2] = 7;
        v[3] = 40;
        v[4] = 12;
        v[5] = 8;

        ZeroOnePackCal obj = new ZeroOnePackCal();
        int[][] dp = obj.getDp(N, W, w, v);
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= W; j++) {
                System.out.printf("(%d,%d)=%-5d", i, j, dp[i][j]);
            }
            System.out.println();
        }

        // 背包能够装入物品的最大值为
        int maxValue = dp[N][W];
        System.out.printf("maxValue=%d", maxValue);
        System.out.println();
        // 逆推找出装入背包的所有商品的编号
        int j = W;
        String numStr = "";
        for (int i = N; i > 0; i--) {
            // 若dp[i][j]>dp[i-1][j], 则说明第i件物品放入背包
            if (dp[i][j] > dp[i - 1][j]) {
                numStr = i + " " + numStr;
                j = j - w[i];
            }
            if (j <= 0) {
                break;
            }
        }

        System.out.printf("goods=%s", numStr);
    }

}

运行结果为：

(0,0)=0    (0,1)=0    (0,2)=0    (0,3)=0    (0,4)=0    (0,5)=0    (0,6)=0    (0,7)=0    (0,8)=0    
(1,0)=0    (1,1)=0    (1,2)=0    (1,3)=0    (1,4)=0    (1,5)=0    (1,6)=48   (1,7)=48   (1,8)=48   
(2,0)=0    (2,1)=7    (2,2)=7    (2,3)=7    (2,4)=7    (2,5)=7    (2,6)=48   (2,7)=55   (2,8)=55   
(3,0)=0    (3,1)=7    (3,2)=7    (3,3)=7    (3,4)=7    (3,5)=40   (3,6)=48   (3,7)=55   (3,8)=55   
(4,0)=0    (4,1)=7    (4,2)=12   (4,3)=19   (4,4)=19   (4,5)=40   (4,6)=48   (4,7)=55   (4,8)=60   
(5,0)=0    (5,1)=8    (5,2)=15   (5,3)=20   (5,4)=27   (5,5)=40   (5,6)=48   (5,7)=56   (5,8)=63   
maxValue=63
goods=1 2 5

3.2 计算最优值时记录选取物品列表

在计算背包价值最大值时，我们可以同时记录选取的物品列表。具体实现为：

package com.test.packalgorithm;

import com.google.common.collect.Lists;
import org.apache.commons.collections4.map.MultiKeyMap;

import java.util.List;
import java.util.Objects;

/**
 * 0-1 背包
 */
public class ZeroOnePackRecord {

    /**
     * 获取最大价值
     *
     * @param N 物品个数
     * @param W 背包最大承重
     * @param weight 物品重量数组
     * @param value 物品价值数组
     * @param ij2Goods 选择的商品列表
     * @return 最大价值
     */
    public int[][] getDp(int N, int W,  int[] weight, int[] value, MultiKeyMap<Integer, List<Integer>> ij2Goods) {
        // 定义一个数组dp[i][j]  i表示当前物品的序号, j表示当前书包的重量
        int[][] dp = new int[N + 1][W + 1];
        for (int j = 0; j <= W; j++) {  // 物品不存在时，最大价值肯定是0
            dp[0][j] = 0;
        }
        for (int i = 1; i <= N; i++) {  // 背包重量为0时，最大价值肯定是0
            dp[i][0] = 0;
        }

        for (int i = 1; i <= N; i++) {  // 从第1个物品开始选
            for (int j = 1; j <= W; j++) {
                // 初始化 dp[i][j]
                dp[i][j] = dp[i - 1][j];
                List<Integer> preGoods = ij2Goods.get(i - 1, j);
                if (Objects.isNull(preGoods)) {
                    preGoods = Lists.newArrayList();
                }

                if (weight[i] <= j) { // 若第i件物品重量 小于等于 当前承载重量，则根据价值大小判断是否放入。
                    int ijValue = dp[i - 1][j - weight[i]] + value[i];
                    if ( ijValue > dp[i - 1][j]) {
                        dp[i][j] = ijValue;
                        preGoods = ij2Goods.get(i - 1, j - weight[i]);
                        if (Objects.isNull(preGoods)) {
                            preGoods = Lists.newArrayList();
                        }
                        List<Integer> goods = Lists.newArrayList();
                        goods.addAll(preGoods);
                        goods.add(i);
                        ij2Goods.put(i, j, goods);
                    } else {
                        ij2Goods.put(i, j, preGoods);
                    }
                } else { // 第i件物品重量大于当前承载重量，则不放入。
                    ij2Goods.put(i, j, preGoods);
                }
            }
        }

        return dp;
    }

    public static void main(String[] args) {
        int N = 5; // 物品个数
        int W = 8; // 背包承载最大重量
        int[] w = new int[N + 1]; //表示每件物品的重量（为方便理解，下标从1开始）
        w[1] = 6;
        w[2] = 1;
        w[3] = 5;
        w[4] = 2;
        w[5] = 1;
        int[] v = new int[N + 1]; //表示每件物品的价值（为方便理解，下标从1开始）
        v[1] = 48;
        v[2] = 7;
        v[3] = 40;
        v[4] = 12;
        v[5] = 8;

        MultiKeyMap<Integer, List<Integer>> ij2Goods = new MultiKeyMap<>();
        ZeroOnePackRecord obj = new ZeroOnePackRecord();
        int[][] dp = obj.getDp(N, W, w, v, ij2Goods);

        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= W; j++) {
                System.out.printf("(%d,%d)=%-8d", i, j, dp[i][j]);
            }
            System.out.println();
        }
        // 背包能够装入物品的最大值为
        int maxValue = dp[N][W];
        System.out.printf("maxValue=%d", maxValue);
        System.out.println();

        // 找出装入背包的所有商品的编号
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= W; j++) {
                System.out.printf("(%d,%d)=%-8s", i, j, ij2Goods.get(i, j).toString());
            }
            System.out.println();
        }
        System.out.printf("goods=%s", ij2Goods.get(N, W));
    }
}

运行结果为：

(0,0)=0       (0,1)=0       (0,2)=0       (0,3)=0       (0,4)=0       (0,5)=0       (0,6)=0       (0,7)=0       (0,8)=0       
(1,0)=0       (1,1)=0       (1,2)=0       (1,3)=0       (1,4)=0       (1,5)=0       (1,6)=48      (1,7)=48      (1,8)=48      
(2,0)=0       (2,1)=7       (2,2)=7       (2,3)=7       (2,4)=7       (2,5)=7       (2,6)=48      (2,7)=55      (2,8)=55      
(3,0)=0       (3,1)=7       (3,2)=7       (3,3)=7       (3,4)=7       (3,5)=40      (3,6)=48      (3,7)=55      (3,8)=55      
(4,0)=0       (4,1)=7       (4,2)=12      (4,3)=19      (4,4)=19      (4,5)=40      (4,6)=48      (4,7)=55      (4,8)=60      
(5,0)=0       (5,1)=8       (5,2)=15      (5,3)=20      (5,4)=27      (5,5)=40      (5,6)=48      (5,7)=56      (5,8)=63      
maxValue=63
(1,1)=[]      (1,2)=[]      (1,3)=[]      (1,4)=[]      (1,5)=[]      (1,6)=[1]     (1,7)=[1]     (1,8)=[1]     
(2,1)=[2]     (2,2)=[2]     (2,3)=[2]     (2,4)=[2]     (2,5)=[2]     (2,6)=[1]     (2,7)=[1, 2]  (2,8)=[1, 2]  
(3,1)=[2]     (3,2)=[2]     (3,3)=[2]     (3,4)=[2]     (3,5)=[3]     (3,6)=[1]     (3,7)=[1, 2]  (3,8)=[1, 2]  
(4,1)=[2]     (4,2)=[4]     (4,3)=[2, 4]  (4,4)=[2, 4]  (4,5)=[3]     (4,6)=[1]     (4,7)=[1, 2]  (4,8)=[1, 4]  
(5,1)=[5]     (5,2)=[2, 5]  (5,3)=[4, 5]  (5,4)=[2, 4, 5](5,5)=[3]     (5,6)=[1]     (5,7)=[1, 5]  (5,8)=[1, 2, 5]
goods=[1, 2, 5]

3.3 优化0-1背包解法

通过分析可以发现，已知背包承重j，在新选取一个物品i时，只需要将“选取物品i后背包价值”与“前i-1个物品的背包最大价值”进行比较，即可得出选取物品i后背包最大价值。据此，我们可以将记录背包最大价值的二维数组简化为一位数组，获得优化后的状态转移方程：

当前物品i的重量weight[i]大于背包承重j时，背包最大价值为：

dp[i][j] = dpPre[j]

当前物品i的重量weight[i]小于等于背包承重j时，背包最大价值为：

dp[j] = Math.max(dpPre[j - weight[i]] + value[i] , dpPre[j])

其中，dp[j]表示背包承重为j时前i件物品的背包最大价值，dpPre[j]表示背包承重为j时前i-1件物品的背包最大价值。

具体实现如下：

package com.test.packalgorithm;

import com.google.common.collect.Lists;
import org.apache.commons.collections4.map.MultiKeyMap;

import java.util.Arrays;
import java.util.List;
import java.util.Objects;

/**
 * 0-1 背包
 */
public class ZeroOnePackRecordOpt {

    /**
     * 获取最大价值
     *
     * @param N        物品个数
     * @param W        背包最大承重
     * @param weight   物品重量数组
     * @param value    物品价值数组
     * @param ij2Goods 选择的商品列表
     * @return 最大价值
     */
    public int[] getDp(int N, int W, int[] weight, int[] value, MultiKeyMap<Integer, List<Integer>> ij2Goods, MultiKeyMap<Integer, Integer> ij2Dp) {
        int[] dp = new int[W + 1]; // 前i件物品的背包价值
        int[] dpPre = new int[W + 1];  // 前i-1件物品的背包价值
        for (int j = 0; j <= W; j++) {  // 物品不存在时，背包最大价值肯定是0
            dp[j]= dpPre[j]= 0;
        }

        for (int i = 1; i <= N; i++) {  // 从第1个物品开始选
            for (int j = 1; j <= W; j++) {
                List<Integer> preGoods = ij2Goods.get(i - 1, j);
                if (Objects.isNull(preGoods)) {
                    preGoods = Lists.newArrayList();
                }

                if (weight[i] <= j) { // 第i件物品重量 小于等于 当前承载重量，根据价值大小判断是否放入。
                    int ijValue = dpPre[j - weight[i]] + value[i];
                    if (ijValue > dpPre[j]) {
                        dp[j] = ijValue;
                        preGoods = ij2Goods.get(i - 1, j - weight[i]);
                        if (Objects.isNull(preGoods)) {
                            preGoods = Lists.newArrayList();
                        }
                        List<Integer> goods = Lists.newArrayList();
                        goods.addAll(preGoods);
                        goods.add(i);
                        ij2Goods.put(i, j, goods);
                        ij2Dp.put(i, j, dp[j]);
                    } else {
                        ij2Goods.put(i, j, preGoods);
                        ij2Dp.put(i, j, dpPre[j]);
                    }
                } else { // 第i件物品重量大于当前承载重量，则不放入。
                    ij2Goods.put(i, j, preGoods);
                    ij2Dp.put(i, j, dpPre[j]);
                }
            }

            for (int j = 1; j <= W; j++) {
                dpPre[j] = dp[j];
            }
        }

        return dp;
    }


    public static void main(String[] args) {
        int N = 5; // 物品个数
        int W = 8; // 背包承载最大重量
        int[] w = new int[N + 1]; //表示每件物品的重量（为方便理解，下标从1开始）
        w[1] = 6;
        w[2] = 1;
        w[3] = 5;
        w[4] = 2;
        w[5] = 1;
        int[] v = new int[N + 1]; //表示每件物品的价值（为方便理解，下标从1开始）
        v[1] = 48;
        v[2] = 7;
        v[3] = 40;
        v[4] = 12;
        v[5] = 8;

        MultiKeyMap<Integer, Integer> ij2Dp =  new MultiKeyMap<>();
        MultiKeyMap<Integer, List<Integer>> ij2Goods = new MultiKeyMap<>();
        ZeroOnePackRecordOpt obj = new ZeroOnePackRecordOpt();
        int[] dp = obj.getDp(N, W, w, v, ij2Goods, ij2Dp);
        System.out.println("dp=" + Arrays.toString(dp));
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= W; j++) {
                if (Objects.nonNull(ij2Dp.get(i, j))) {
                    System.out.printf("(%d,%d)=%-5s", i, j, ij2Dp.get(i, j).toString());
                } else {
                    System.out.printf("(%d,%d)=%-5s", i, j, "");
                }
            }
            System.out.println();
        }
        // 背包能够装入物品的最大重量为
        int maxValue = dp[W];
        System.out.printf("maxValue=%d", maxValue);
        System.out.println();

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= W; j++) {
                System.out.printf("(%d,%d)=%-5s", i, j, ij2Goods.get(i, j).toString());
            }
            System.out.println();
        }
        System.out.printf("goods=%s\n", ij2Goods.get(N, W));
    }
}

运行结果为：文章来源地址https://www.toymoban.com/news/detail-405805.html

dp=[0, 8, 15, 20, 27, 40, 48, 56, 63]
(1,1)=0    (1,2)=0    (1,3)=0    (1,4)=0    (1,5)=0    (1,6)=48   (1,7)=48   (1,8)=48   
(2,1)=7    (2,2)=7    (2,3)=7    (2,4)=7    (2,5)=7    (2,6)=48   (2,7)=55   (2,8)=55   
(3,1)=7    (3,2)=7    (3,3)=7    (3,4)=7    (3,5)=40   (3,6)=48   (3,7)=55   (3,8)=55   
(4,1)=7    (4,2)=12   (4,3)=19   (4,4)=19   (4,5)=40   (4,6)=48   (4,7)=55   (4,8)=60   
(5,1)=8    (5,2)=15   (5,3)=20   (5,4)=27   (5,5)=40   (5,6)=48   (5,7)=56   (5,8)=63   
maxValue=63
(1,1)=[]   (1,2)=[]   (1,3)=[]   (1,4)=[]   (1,5)=[]   (1,6)=[1]  (1,7)=[1]  (1,8)=[1]  
(2,1)=[2]  (2,2)=[2]  (2,3)=[2]  (2,4)=[2]  (2,5)=[2]  (2,6)=[1]  (2,7)=[1, 2](2,8)=[1, 2]
(3,1)=[2]  (3,2)=[2]  (3,3)=[2]  (3,4)=[2]  (3,5)=[3]  (3,6)=[1]  (3,7)=[1, 2](3,8)=[1, 2]
(4,1)=[2]  (4,2)=[4]  (4,3)=[2, 4](4,4)=[2, 4](4,5)=[3]  (4,6)=[1]  (4,7)=[1, 2](4,8)=[1, 4]
(5,1)=[5]  (5,2)=[2, 5](5,3)=[4, 5](5,4)=[2, 4, 5](5,5)=[3]  (5,6)=[1]  (5,7)=[1, 5](5,8)=[1, 2, 5]
goods=[1, 2, 5]

到了这里，关于背包问题之0-1背包算法详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！