---
title: "混合背包问题"
created: 2025-11-28
tags:
  - 算法
---

# 混合背包问题

## 题目 [**混合背包问题**](https://www.acwing.com/problem/content/7/)

![[image-2eca4b0d.png]]

## 思路分析

学过了01背包 完全背包 多重背包

不难发现他们都是极其相似的

首先01背包用的是从大到小枚举体积 因为它要用的是上一层的数据

完全背包用的是第i层的数据 由此使用从小到大枚举体积

而多重背包有两种理解方式 一是把它当成01背包看 先把所有物品用二进制优化 拆分成多个01背包里的物品 写法就和01完全一样了 从大到小枚举体积
二是当成完全背包来看 把所有的mod余相等的当做同一类物品 这些物品之间相互独立 只需要使用滑动窗口取出每一类中的最大值即可

这里多重背包还是选择使用二进制好些 更容易理解

使用二进制优化的多重背包 与01背包是完全一样的 那么如何合并起来呢

发现01背包不过就是某类物品只能选一次的多重背包吧（s[i]=1)

那么问题就基本解决了

三个问题变成了两个问题

碰到完全背包（无限选的）用一种写法

碰到01背包把它变成s[i]=1的多重背包 再把多重背包进行二进制拆分 合起来用一种写法

![[image-87e815b9.png]]

## 代码实现

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

using namespace std;

const int N=1010;

struct Thing{

    int kind;

    int v,w;

};

vector<Thing> things;

int dp[N];

int n,m;

int main()

{

    cin>>n>>m;

    for(int i=1;i<=n;i++){

        int v,w,s;

        cin>>v>>w>>s;

        if(s==-1)//如果该物品是01背包的 存-1标记

            things.push_back({-1,v,w});

        else if(s==0)

            things.push_back({0,v,w});

        else{//如果是多重背包的 把它拆成多个01背包

            for(int k=1;k<=s;k*=2){

                things.push_back({-1,v*k,w*k});

                s-=k;

            }

            if(s>0)

                things.push_back({-1,v*s,w*s});

        }

    }

    for(auto thing:things){

        if(thing.kind==-1)

            for(int j=m;j>=thing.v;j--)//01背包 从大到小

                dp[j]=max(dp[j],dp[j-thing.v]+thing.w);

        else

            for(int j=thing.v;j<=m;j++)//完全背包 从小到大

                dp[j]=max(dp[j],dp[j-thing.v]+thing.w);

    }

    cout<<dp[m];

    return 0;

}
```

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

using namespace std;

const int N=1010;

int v[N],w[N],s[N];

int dp[N];

int n,m;

int main()

{

    cin>>n>>m;

    for(int i=1;i<=n;i++){

        cin>>v[i]>>w[i]>>s[i];

    }

    //可以不用事先存好 直接现做

    for(int i=1;i<=n;i++){

        if(s[i]==0)//完全背包 从小到大

            for(int j=v[i];j<=m;j++)

                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

        else//01和多重合在一起

        {

            if(s[i]==-1)

                s[i]=1;//01背包就是该物品只能选一次的情况 直接让s[i]>0 且等于1即可

            for(int k=1;k<=s[i];k*=2){

                for(int j=m;j>=k*v[i];j--){

                    dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);

                }

                s[i]-=k;

            }

            if(s[i]){

                for(int j=m;j>=s[i]*v[i];j--){

                    dp[j]=max(dp[j],dp[j-s[i]*v[i]]+s[i]*w[i]);

                }

            }

        }

    }

    cout<<dp[m];

    return 0;

}

//思路虽然更巧妙 直接一气呵成 但是效率反而更低了些 上面138ms 这个166ms

//这个写法用于练手，深入理解用 真正写这类题的话还是用上面的stl 条理清晰
```

## 同类题型

## 视频讲解

---
⬅️ [[有依赖的背包问题|有依赖的背包问题]] 🏠 [[00-刷题理模型]] ➡️ [[包子凑数（未解决）|包子凑数（未解决）]]