背包问题之完全背包算法详解_完全背包问题

作者：小惠珠哦 | 2024-07-17 13:56:27

踩

完全背包问题

一、完全背包问题描述

有5种物品和1个背包，每种物品的个数是无限的，背包最多只能装下10公斤的物品。怎样选择物品，使得背包能装下并且得到的价值最大。物品的重量、价值如下所示：

物品编号	重量	价值
1	2	6
2	2	3
3	6	5
4	5	4
5	4	6

二、解题思路

我们先看下多重背包实现原理：背包问题之多重背包_爱思考的实践者的博客-CSDN博客

对比分析发现，完全背包与多重背包的差别就是：对物品按种类划分，每种物品的个数不限制。

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

在多重背包状态转移方程的基础上，可以总结出多重背包的状态转移方程：

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

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

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

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

其中，k满足条件： 0 <= k <= j/weight[i]。

三、Java编码实现

根据上一节的状态转移方程，我们很容易就能编程解决多重背包问题。

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

直接按照状态转移方程进行求解，具体实现代码为：


package com.test.packalgorithm;
 
import com.google.common.collect.Maps;
import org.apache.commons.collections4.map.MultiKeyMap;
 
import java.util.Map;
import java.util.Objects;
 
/**
 * 多重背包
 */
public class CompletePackRecord {
 
    /**
     * 获取最大价值
     *
     * @param N 物品种类数
     * @param W 背包最大承重
     * @param weight 物品重量数组
     * @param value 物品价值数组
     * @param ij2Goods 选择的商品列表
     * @return 最大价值
     */
    public int[][] getDp(int N, int W,  int[] weight, int[] value, MultiKeyMap<Integer, Map<Integer, 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];
                Map<Integer, Integer> preGoods = ij2Goods.get(i - 1, j);
                if (Objects.isNull(preGoods)) {
                    preGoods = Maps.newHashMap();
                }
 
                if (weight[i] <= j) { // 第i类物品重量 小于等于 当前承载重量，根据价值大小判断是否放入。
                    // 考虑物品的件数限制, 寻找dp[i][j]的最大值
                    int maxNumber = j / weight[i];
                    for (int k = 0; k <= maxNumber; k++) {
                        int ijkValue = dp[i - 1][j - (k * weight[i])] + (k * value[i]);
                        dp[i][j] = Math.max(dp[i][j], ijkValue);
                    }
 
                    if (dp[i][j] > dp[i - 1][j]) {
                        int k;
                        for (k = 0; k <= maxNumber; k++) {
                            int ijValue = dp[i - 1][j - (k * weight[i])] + (k * value[i]);
                            if (dp[i][j] == ijValue) {
                                break;
                            }
                        }
 
                        preGoods = ij2Goods.get(i - 1, j - (k * weight[i]));
                        if (Objects.isNull(preGoods)) {
                            preGoods = Maps.newHashMap();
                        }
                        Map<Integer, Integer> goods = Maps.newHashMap();
                        goods.putAll(preGoods);
                        goods.put(i, k);
                        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 = 10; // 背包最大承载重量
 
        int[] w = new int[N + 1]; // 每件物品的重量，为方便理解，下标从1开始
        w[1] = 2;
        w[2] = 2;
        w[3] = 6;
        w[4] = 5;
        w[5] = 4;
        int[] v = new int[N + 1]; // 每件物品的价值
        v[1] = 6;
        v[2] = 3;
        v[3] = 5;
        v[4] = 4;
        v[5] = 6;
 
        MultiKeyMap<Integer, Map<Integer, Integer>> ij2Goods = new MultiKeyMap<>();
        CompletePackRecord obj = new CompletePackRecord();
        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)=%-5d", 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.println("goods:");
        ij2Goods.get(N, W).forEach((key, value)-> System.out.printf("key=%d, value=%d\n", key, value));
    }
}

运行结果为：


(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    (0,9)=0    (0,10)=0    
(1,0)=0    (1,1)=0    (1,2)=6    (1,3)=6    (1,4)=12   (1,5)=12   (1,6)=18   (1,7)=18   (1,8)=24   (1,9)=24   (1,10)=30   
(2,0)=0    (2,1)=0    (2,2)=6    (2,3)=6    (2,4)=12   (2,5)=12   (2,6)=18   (2,7)=18   (2,8)=24   (2,9)=24   (2,10)=30   
(3,0)=0    (3,1)=0    (3,2)=6    (3,3)=6    (3,4)=12   (3,5)=12   (3,6)=18   (3,7)=18   (3,8)=24   (3,9)=24   (3,10)=30   
(4,0)=0    (4,1)=0    (4,2)=6    (4,3)=6    (4,4)=12   (4,5)=12   (4,6)=18   (4,7)=18   (4,8)=24   (4,9)=24   (4,10)=30   
(5,0)=0    (5,1)=0    (5,2)=6    (5,3)=6    (5,4)=12   (5,5)=12   (5,6)=18   (5,7)=18   (5,8)=24   (5,9)=24   (5,10)=30   
maxValue=30
(1,1)={}      (1,2)={1=1}   (1,3)={1=1}   (1,4)={1=2}   (1,5)={1=2}   (1,6)={1=3}   (1,7)={1=3}   (1,8)={1=4}   (1,9)={1=4}   (1,10)={1=5}   
(2,1)={}      (2,2)={1=1}   (2,3)={1=1}   (2,4)={1=2}   (2,5)={1=2}   (2,6)={1=3}   (2,7)={1=3}   (2,8)={1=4}   (2,9)={1=4}   (2,10)={1=5}   
(3,1)={}      (3,2)={1=1}   (3,3)={1=1}   (3,4)={1=2}   (3,5)={1=2}   (3,6)={1=3}   (3,7)={1=3}   (3,8)={1=4}   (3,9)={1=4}   (3,10)={1=5}   
(4,1)={}      (4,2)={1=1}   (4,3)={1=1}   (4,4)={1=2}   (4,5)={1=2}   (4,6)={1=3}   (4,7)={1=3}   (4,8)={1=4}   (4,9)={1=4}   (4,10)={1=5}   
(5,1)={}      (5,2)={1=1}   (5,3)={1=1}   (5,4)={1=2}   (5,5)={1=2}   (5,6)={1=3}   (5,7)={1=3}   (5,8)={1=4}   (5,9)={1=4}   (5,10)={1=5}   
goods:
key=1, value=5

3.2 优化求解背包最大价值与选取物品列表

当前物品i的重量weight[i]小于等于背包承重j时，对状态转移方程进行分析，可以发现：

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

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

其中，k满足条件： 0 <= k <= j/weight[i]。

对比分析以上两个公式，可以推导出新的状态转移方程：

dp[i][j] = Math.max(dp[i-1][j]，dp[i][j-weight[i]] + value[i]）

据此，可以对朴素求解完全背包算法进行优化，具体实现为：


package com.test.packalgorithm;
 
import com.google.common.collect.Maps;
import org.apache.commons.collections4.map.MultiKeyMap;
 
import java.util.Map;
import java.util.Objects;
 
/**
 * 多重背包
 */
public class CompletePackRecordOpt {
 
    /**
     * 获取最大价值
     *
     * @param N 物品种类数
     * @param W 背包最大承重
     * @param weight 物品重量数组
     * @param value 物品价值数组
     * @param ij2Goods 选择的商品列表
     * @return 最大价值
     */
    public int[][] getDp(int N, int W, int[] weight, int[] value, MultiKeyMap<Integer, Map<Integer, 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];
                Map<Integer, Integer> preGoods = ij2Goods.get(i - 1, j);
                if (Objects.isNull(preGoods)) {
                    preGoods = Maps.newHashMap();
                }
 
                if (weight[i] <= j) { // 第i类物品重量 小于等于 当前承载重量，根据价值大小判断是否放入。
                    dp[i][j] = Math.max(dp[i][j - weight[i]] + value[i], dp[i][j]);
                    if (dp[i][j] > dp[i - 1][j]) {
                        int maxNumber = j / weight[i];  // 考虑物品的件数限制
                        int k;
                        for (k = 0; k <= maxNumber; k++) {
                            int ijkValue = dp[i - 1][j - (k * weight[i])] + (k * value[i]);
                            if (dp[i][j] == ijkValue) {
                                break;
                            }
                        }
 
                        preGoods = ij2Goods.get(i - 1, j - (k * weight[i]));
                        if (Objects.isNull(preGoods)) {
                            preGoods = Maps.newHashMap();
                        }
                        Map<Integer, Integer> goods = Maps.newHashMap();
                        goods.putAll(preGoods);
                        goods.put(i, k);
                        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 = 10; // 背包最大承载重量
 
        int[] w = new int[N + 1]; // 每件物品的重量，为方便理解，下标从1开始
        w[1] = 2;
        w[2] = 2;
        w[3] = 6;
        w[4] = 5;
        w[5] = 4;
        int[] v = new int[N + 1]; // 每件物品的价值
        v[1] = 6;
        v[2] = 3;
        v[3] = 5;
        v[4] = 4;
        v[5] = 6;
        MultiKeyMap<Integer, Map<Integer, Integer>> ij2Goods = new MultiKeyMap<>();
        CompletePackRecordOpt obj = new CompletePackRecordOpt();
        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)=%-5d", 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.println("goods:");
        ij2Goods.get(N, W).forEach((key, value) -> System.out.printf("key=%d, value=%d\n", key, value));
    }
}

运行结果为：


(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    (0,9)=0    (0,10)=0    
(1,0)=0    (1,1)=0    (1,2)=6    (1,3)=6    (1,4)=12   (1,5)=12   (1,6)=18   (1,7)=18   (1,8)=24   (1,9)=24   (1,10)=30   
(2,0)=0    (2,1)=0    (2,2)=6    (2,3)=6    (2,4)=12   (2,5)=12   (2,6)=18   (2,7)=18   (2,8)=24   (2,9)=24   (2,10)=30   
(3,0)=0    (3,1)=0    (3,2)=6    (3,3)=6    (3,4)=12   (3,5)=12   (3,6)=18   (3,7)=18   (3,8)=24   (3,9)=24   (3,10)=30   
(4,0)=0    (4,1)=0    (4,2)=6    (4,3)=6    (4,4)=12   (4,5)=12   (4,6)=18   (4,7)=18   (4,8)=24   (4,9)=24   (4,10)=30   
(5,0)=0    (5,1)=0    (5,2)=6    (5,3)=6    (5,4)=12   (5,5)=12   (5,6)=18   (5,7)=18   (5,8)=24   (5,9)=24   (5,10)=30   
maxValue=30
(1,1)={}      (1,2)={1=1}   (1,3)={1=1}   (1,4)={1=2}   (1,5)={1=2}   (1,6)={1=3}   (1,7)={1=3}   (1,8)={1=4}   (1,9)={1=4}   (1,10)={1=5}   
(2,1)={}      (2,2)={1=1}   (2,3)={1=1}   (2,4)={1=2}   (2,5)={1=2}   (2,6)={1=3}   (2,7)={1=3}   (2,8)={1=4}   (2,9)={1=4}   (2,10)={1=5}   
(3,1)={}      (3,2)={1=1}   (3,3)={1=1}   (3,4)={1=2}   (3,5)={1=2}   (3,6)={1=3}   (3,7)={1=3}   (3,8)={1=4}   (3,9)={1=4}   (3,10)={1=5}   
(4,1)={}      (4,2)={1=1}   (4,3)={1=1}   (4,4)={1=2}   (4,5)={1=2}   (4,6)={1=3}   (4,7)={1=3}   (4,8)={1=4}   (4,9)={1=4}   (4,10)={1=5}   
(5,1)={}      (5,2)={1=1}   (5,3)={1=1}   (5,4)={1=2}   (5,5)={1=2}   (5,6)={1=3}   (5,7)={1=3}   (5,8)={1=4}   (5,9)={1=4}   (5,10)={1=5}   
goods:
key=1, value=5

四、总结

完全背包状态转移方程与多重背包状态转移方程几乎一样，差别只在于物品件数没有限制。在理解0-1背包和多重背包后，理解完全背包就很简单了。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小惠珠哦/article/detail/840255