$$\color{Red}{多重背包:三种语言+(迭代版和物理版)二进制分堆}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

1.算法优化和细节

• 最首先应该想到：为什么不能利用之前的完全背包问题的思路错位相减解决问题？

我们不妨再次分析一下此时如何优化最内层的循环
完全背包问题：

f[i , j] =  max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)

不难发现，f[i][j-v] + w即为第一个式子除第一项右边的部分,故由此可得：
f[i][j] = max( f[i-1][j], f[i,j-v] + w )

多重背包问题：

f[i,j] =  max(f[i-1,j],f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , ...，f[i-1,j-sv] + sw )
f[i,j-v]= max(         f[i-1,j-v]   , f[i-1,j-2*v] + w , ...，f[i-1,j-sv] + (s-1)w, f[i-1,j-(s + 1) * v] + sw )

• 为什么此时会多出一项？

完全背包问题，可以在背包容量允许的情况下，一直增加该物品数目，所以上面的式子后面的无穷代表的取极限的情况，故直接可以等价到上面的右部分
而多重背包问题，不管容量怎么样，我们最多也就挑s[i]个物品，那么就导致着注定f[i, j-v]会多出挑到第s[i]个对应的冗余项，故此方法失效

• 由此引出我们对这个问题的解决办法——二进制分堆

如果一个物品有十个，理论上我们要进行10次判断，才可以最后跳出对这个物品挑几个的循环，如果目标是7个，7以后的判断其实会拉长整个程序的时间，如果我们把整个区间压缩到更小，每个区间代表着一堆同个物品，只要满足可以用这一堆堆物品可以表示出原本的总数的所有情况，那么化为01背包的时候，就可以用更小的区间，却满足更大的数量范围。

二进制分堆：将一个区间如10：划分为1， 2， 4， 3（不足进位就直接落位），理论上我们可以用这四个数组表示所有的1-10的数字，那么我们就可以用分堆加01背包的思路解决问题

• 为什么能表示出所有数字就没问题？难道不会出现先判的差错？

举个例子：如果最优是4，第一次判断堆1(i = 1)，取了更好，第二次判断堆2(i = 2)，堆1 堆2都取好， 第二次判断堆3(i = 3)，堆1 堆2不取，只取堆4好 .....
并不会因为更小的i取了堆1堆2，导致我们判断i=3的时候从已经取了堆1，堆2考虑，而是先从整个背包去除v[3]（相当于先取了堆4)再去考虑怎么取

java 物理分堆

import java.io.*;

public class Main {
    static int N = 100010, n, m;
    static int f[] = new int[N];
    static int v[] = new int[N];
    static int w[] = new int[N];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1[] = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        //分堆的下标
        int cnt = 1;

        for (int i = 1; i <= n; i++) {
            String s2[] = br.readLine().split(" ");
            int v_ = Integer.parseInt(s2[0]);
            int w_ = Integer.parseInt(s2[1]);
            int s_ = Integer.parseInt(s2[2]);
            int k = 1;//分堆个数
            while(s_ > k){
                v[cnt] = v_ * k;
                w[cnt] = w_ * k;
                s_ -= k;
                k *= 2;
                cnt += 1;
            }
            if(s_ > 0){
                v[cnt] = v_ * s_;
                w[cnt] = w_ * s_;
                cnt += 1;
            }
        }
        for (int i = 1; i <= cnt; i++) {
            for (int j = m; j >=v[i]; j--) {
                    f[j] = Math.max(f[j], f[j-v[i]] + w[i]);
            }
        }
        System.out.println(f[m]);
    }
}

java迭代分堆

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int M = 2010, n, m;
    static int[] f = new int[M];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] str1 = br.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        m = Integer.parseInt(str1[1]);
        for (int i = 1; i <= n; i++) {
            String[] str2 = br.readLine().split(" ");
            int v = Integer.parseInt(str2[0]);
            int w = Integer.parseInt(str2[1]);
            int s = Integer.parseInt(str2[2]);
            for (int k = 1; k <= s; k *= 2) {
                for (int j = m; j >= k * v; j--) 
                    f[j] = Math.max(f[j], f[j - k * v] + k * w);
                s -= k;
            }
            if (s > 0)
                for (int j = m; j >= s * v; j--)
                    f[j] = Math.max(f[j], f[j - s * v] + s * w);
        }
        System.out.println(f[m]);
    }
}

python3代码

N = 12010
v = [0] * N
w = [0] * N
f = [0] * N

n, m = map(int, input().split())
cnt = 1
# n件不同物品，按数量依次分堆
for i in range(n):
    v_, w_, s_ = map(int, input().split())
    k = 1
    #二进制分堆
    while s_ >= k:
        v[cnt] = k * v_
        w[cnt] = k * w_
        cnt += 1
        s_ -= k
        k *= 2
    #最后一堆判断
    if s_ > 0:
        v[cnt] = s_ * v_
        w[cnt] = s_ * w_
        cnt += 1

#转化为01背包问题,此时cnt才为总数，每堆物品为一系列物品的集合
for i in range(1, cnt+1):
    for j in range(m, v[i] - 1, -1):
        f[j] = max(f[j], f[j - v[i]] + w[i])

print(f[m])

C++具体代码

#include <iostream>

using namespace std;

const int N = 12010, M = 2010;
int v[N], w[N];
int dp[N];

int main()
{
    int n, m, cnt = 0;//cnt存储实际分组的组别下标
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)
    {
        int a, b, s;//暂存物品属性
        scanf("%d%d%d", &a, &b, &s);
        int k = 1;//2的零次方。这里也可以看成每组数量
        while(s >= k)
        {
            cnt ++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;//总数缩小
            k *= 2;//指数增加下一组的数量
        }
        //最后一组可能不够指数倍增的大小
        if(s > 0)
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    //此时组数已经变成了cnt的大小，使用01背包模板
    for(int i=1; i<=cnt; i++)
        for(int j=m; j>=v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << dp[m] << endl;
    return 0;
}