$$\color{Red}{多重背包问题:三种语言+朴素版+强行拆01背包版}$$

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

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

题目介绍

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi
。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围

0 < N, V ≤ 100

0 < vi, wi, si ≤ 100

输入样例：

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

方法一：朴素版代码思想

与完全背包问题类似，但是我们在第二重循环对状态方程赋值时，max()内应该是能放下1-k个（k即最多个数）的表达式。
为了解决写出如此庞杂的表达式，可以直接调用一层for循环。而为了避免出现超过可使用数目，循环中加入限制条件k<=s[i]

1.具体代码

此方法复杂度太高，只适合数据量小的情况

 for(int i=1; i<=n; i++)
        for(int j=0; j<=m; j++)
            for(int k=0; k<=s[i] && k*v[i]<=j; k++)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);

为什么不是dp[i][j] = max(dp[i-1][j], dp[i-1][j-k * v[i]]+k * w[i]);
当k等于0时，即是dp[i-1][j]
同时在k次循环当中，写入自己是完成对k的所有取值的不断刷新，如果改完刷新dp[i][j]的值每次只和dp[i-1][j]比较

java 二维

import java.util.*;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i=1; i<=n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
            s[i] = sc.nextInt();
        }
        for(int i=1; i<=n; i++)
            for(int j=0; j<=m; j++)
                for(int k=0; k<=s[i]; k++){
                    if (j >= k * v[i])
                        f[i][j] = Math.max(f[i][j], f[i-1][j - k*v[i]] + k * w[i]);
                    else
                        break;
                }

        System.out.println(f[n][m]);
    }
}

python3 二维01

N = 110
v = [0] * N
s = [0] * N
w = [0] * N
f = [[0] * N for i in range(N)]

n, m = map(int, input().split())
for i in range(1, n+1):
    v[i], w[i], s[i] = map(int, input().split())

#dp数组生成
for i in range(1, n+1):
    for j in range(m+1):
        for k in range(s[i]+1):
            if j >= k * v[i]:
                f[i][j] = max(f[i][j], f[i-1][j - k * v[i]] + k * w[i])
            else:
                break
print(f[n][m])

python 一维优化

N = 110
v = [0] * N
w = [0] * N
s = [0] * N
f = [0] * N

n, m = map(int, input().split())
for i in range(1, n+1):
    v[i], w[i], s[i] = map(int, input().split())    

for i in range(1, n+1):
    for j in range(m, v[i]-1, -1):
        for k in range(s[i] + 1):
            if j >= k * v[i]:
                f[j] = max(f[j], f[j - k * v[i]] + k * w[i])
            else:
                break
print(f[m])

方法二：强行拆为01背包问题

在数据量小的情况下，我们不妨把每个商品的s[i]个数目干脆拆分为s[i]个物品，使得dp的规划变成商品增大的01背包

2.具体代码

#include <iostream>
using namespace std;

const int N = 10000;
int w[N], v[N], dp[N];

int main()
{
    int n, m, a, b, c;//abc暂存每个物品的实际属性
    scanf("%d%d", &n, &m);

    int t=1;//生成01背包的第一个物品下标
    while(n--)
    {
       scanf("%d%d%d", &a, &b, &c); 
       while(c--)
       {
           v[t] = a;
           w[t++] = b;
       }
    }
    //化为01背包的问题
    for(int i=1; i<=t; i++)//背包扩容到t大小了
        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;
}