一、多重背包问题描述

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

二、解题思路

我们先看下0-1背包实现原理：背包问题之0-1背包算法详解_爱思考的实践者的博客-CSDN博客。

对比分析发现，多重背包与0-1背包的差别就是：对物品按种类划分，每种物品指定件数。

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

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

当前物品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 < number[i] 并且 0 <= k <= j/weight[i]。

三、Java编码实现

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

具体实现代码为：

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 ManyPacksRecord {

    /**
     * 获取最大价值
     *
     * @param N 物品个数
     * @param W 背包最大承重
     * @param weight 物品重量数组
     * @param value 物品价值数组
     * @param number 物品个数数组
     * @param ij2Goods 选择的商品列表
     * @return 最大价值
     */
    public int[][] getDp(int N, int W, int[] weight, int[] value, int[] number, 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类物品重量 小于等于 当前承载重量，根据价值大小判断是否放入。
                    // 考虑物品的件数限制
                    int maxNumber = Math.min(number[i], 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 = 3; // 商品种类数
        int W = 15; // 背包最大承载重量

        int[] w = new int[N + 1]; // 每件物品的重量，为方便理解，下标从1开始
        w[1] = 3;
        w[2] = 4;
        w[3] = 5;
        int[] v = new int[N + 1]; // 每件物品的价值
        v[1] = 2;
        v[2] = 3;
        v[3] = 4;
        int[] n = new int[N + 1]; // 每件物品的个数
        n[1] = 4;
        n[2] = 3;
        n[3] = 2;

        MultiKeyMap<Integer, Map<Integer, Integer>> ij2Goods = new MultiKeyMap<>();
        ManyPacksRecord obj = new ManyPacksRecord();
        int[][] dp = obj.getDp(N, W, w, v, n, 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.printf("goods=%s", ij2Goods.get(N, W).toString());
    }
}

运行结果如下：

(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    (0,11)=0    (0,12)=0    (0,13)=0    (0,14)=0    (0,15)=0    
(1,0)=0    (1,1)=0    (1,2)=0    (1,3)=2    (1,4)=2    (1,5)=2    (1,6)=4    (1,7)=4    (1,8)=4    (1,9)=6    (1,10)=6    (1,11)=6    (1,12)=8    (1,13)=8    (1,14)=8    (1,15)=8    
(2,0)=0    (2,1)=0    (2,2)=0    (2,3)=2    (2,4)=3    (2,5)=3    (2,6)=4    (2,7)=5    (2,8)=6    (2,9)=6    (2,10)=7    (2,11)=8    (2,12)=9    (2,13)=9    (2,14)=10   (2,15)=11   
(3,0)=0    (3,1)=0    (3,2)=0    (3,3)=2    (3,4)=3    (3,5)=4    (3,6)=4    (3,7)=5    (3,8)=6    (3,9)=7    (3,10)=8    (3,11)=8    (3,12)=9    (3,13)=10   (3,14)=11   (3,15)=11   
maxValue=11
(1,1)={}      (1,2)={}      (1,3)={1=1}   (1,4)={1=1}   (1,5)={1=1}   (1,6)={1=2}   (1,7)={1=2}   (1,8)={1=2}   (1,9)={1=3}   (1,10)={1=3}   (1,11)={1=3}   (1,12)={1=4}   (1,13)={1=4}   (1,14)={1=4}   (1,15)={1=4}   
(2,1)={}      (2,2)={}      (2,3)={1=1}   (2,4)={2=1}   (2,5)={2=1}   (2,6)={1=2}   (2,7)={1=1, 2=1}(2,8)={2=2}   (2,9)={1=3}   (2,10)={1=2, 2=1}(2,11)={1=1, 2=2}(2,12)={2=3}   (2,13)={1=3, 2=1}(2,14)={1=2, 2=2}(2,15)={1=1, 2=3}
(3,1)={}      (3,2)={}      (3,3)={1=1}   (3,4)={2=1}   (3,5)={3=1}   (3,6)={1=2}   (3,7)={1=1, 2=1}(3,8)={2=2}   (3,9)={2=1, 3=1}(3,10)={3=2}   (3,11)={1=1, 2=2}(3,12)={2=3}   (3,13)={2=2, 3=1}(3,14)={2=1, 3=2}(3,15)={1=1, 2=3}
goods={1=1, 2=3}

四、总结

多重背包状态转移方程与0-1背包状态转移方程很类似，差别只在于物品件数的限制，明确了这点，理解起来就简单了。