---
title: "多重背包问题"
description: "多重背包就是在完全背包问题上加入个数限制，然而运用的却是01背包和完全背包的思路QAQ"
canonical_url: "https://yangqiuyi.com/blog/suan-fa/duo-chong-bei-bao-wen-ti"
---

> Index of every page on this site: [llms.txt](https://yangqiuyi.com/llms.txt)

多重背包就是在完全背包问题上加入个数限制，然而运用的却是01背包和完全背包的思路QAQ

## 多重背包I-小数据量

### 问题描述

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

第 i 种物品最多有 s~~i~~ 件，每件体积是 v~~i~~，价值是 w~~i~~。

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

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

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

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

数据范围
0 < N,V ≤ 100
0 < v~~i~~,w~~i~~,s~~i~~ ≤ 100

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10

### 思路

小数据量仅仅在完全背包上加个循环，从0-k枚举，时间复杂度相当大

### Code

```cpp
#include <bits/stdc++.h>

using namespace std;

int f[10005];

int main()
{
    int n,m;
    cin>>n>>m;
    int w[10005],v[10005],s[10005];
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
    for(int i=0;i<=n;i++)
        for(int j=m;j>=v[i];j--)
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
            {
                f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
            }
    cout<<f[m];
    return 0;
}
```

## 多重背包II-大数据

### 问题描述

与[多重背包I](#%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85I-%E5%B0%8F%E6%95%B0%E6%8D%AE%E9%87%8F)没有太大区别，仅仅是数据范围扩大了
0 < N ≤ 1000
0 < V ≤ 2000
0 < v~~i~~,w~~i~~,s~~i~~ ≤ 2000

题目给出提示：

> 提示：
> 本题考查多重背包的二进制优化方法。

### 思考

我们可以用1和2搭配出0-3之间的任意数，
可以用1，2，4搭配出0-7中的任意数
以此类推，我们可以用1,2,4,8,...,2^n^拼凑出0~2×2^n^-1区间内任意一个数，最后，多重背包就转化成了01背包问题。

举个例子：
我们有100个苹果，选择的方式有101种，但是我们可以把100拆成1，2，4，8，16，32，**37**，我们可以用这些数字加出0~100范围内的任意一个整数。
可能你会感到疑惑，为什么最后一个数字是**37**，而不是64。让我们思考一下，假设最后一个数字是64，那我们排列组合之后可以得到127个数字！

把这些苹果的组合看作一个整体，也就是说现在我们有a,b,c,d,e,f,g这七件物品，他们的价值分别是 1，2，4，8，16，32，37，我们可以通过选择要或者不要这七件物品，排列出100只苹果的101种可能。

### Code

```cpp
#include <bits/stdc++.h>

using namespace std;

int f[25000];
int w[25000],v[25000],s[25000];
int main()
{
    int n,m;
    cin>>n>>m;
    int a,b,c;
    int cnt=1;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b>>c;
        int base=1;
        for(;c>=base*2||(c==1&&base==1);base*=2)
        {
            s[cnt]=base;
            w[cnt]=base*b;
            v[cnt]=base*a;
            cnt++;
        }
        if(c>=s[cnt-1]*2)
        {
            s[cnt]=c-s[cnt-1]*2+1;
            w[cnt]=s[cnt]*b;
            v[cnt]=s[cnt]*a;
            cnt++;
        }
    }
    for(int i=0;i<cnt;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}
```

## Sitemap

See the full [sitemap](https://yangqiuyi.com/sitemap.md) for all pages.