动态规划——多重背包问题

写在前面

由于本人实力尚浅，接触算法没多久，写这篇blog仅仅是想要提升自己对算法的理解，如果各位读者发现什么错误，恳请指正，希望和大家一起进步。(●’◡’●)
如果没看过我前面关于01背包问题（良心正解）和完全背包问题（良心正解）的宝宝可以先去看看，可以让你对动态规划的理解更透彻

---

DP核心思路

---

多重背包问题

题目

---

思路

重要变量说明
f[][[]:用于状态表示；
w[]：记录每个物品的价值；
v][]：记录每个物品的体积；
cnt[]:记录每个物品的数量；

1. 定义二维数组f[][],其中f[i][j]表示在前i个物品，背包容积为j的限制下所能装下的最大价值。这里的f[i][j]就是做法的集合，f[i][j]的值就是最大价值即属性。
2. 从i=1开始枚举，对于第i个物品，都有一定数量的选择：
   • 如果不选第i个物品，那么状态转移方程为f[i][j]=f[i-1][j]
   • 如果选择第i个物品一次，那么状态转移方程为f[i][j]=f[i-1][j-v[i]]+w[i]
   • ......
   • 如果选择第i个物品cnt[i]次（即每个物品的最大数量），那么状态转移方程为f[i][j]=max(f[i-1][j-cnt[i]*v[i]]+cnt[i]*w[i](前提是不超过当前背包的容积）
3. 我们因为要求最大价值，所以对上面两种情况去max即可。

代码（不优化）

二维数组

#include<iostream>

using namespace std;
const int N=110;
int v[N],w[N],f[N][N],cnt[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i]>>cnt[i];
    for(int i=1;i<=n;i++)       //i表示当前枚举的物品，从第1个物品开始枚举，直到第n个
        for(int j=1;j<=m;j++)       //j表示当前枚举的容积
            for(int k=0;k<=cnt[i] and k<=j/v[i];k++)        //从0（0表示不选这个物品）开始枚举，并且保证j永远大于k*[i]
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
    cout<<f[n][m]<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

一维数组

二维数组优化到一维数组的具体思路和前面我写的题解思路一模一样，不懂的宝宝可以去看——>01背包问题或者完全背包问题（良心正解）

#include<iostream>   

using namespace std;
const int N=110;
int v[N],w[N],f[N],cnt[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i]>>cnt[i];
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=0;k<=cnt[i] and k<=j/v[i];k++)
                f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
    cout<<f[m]<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

思考

聪明的你一定发现了这个问题和01背包问题非常像，如果我们把数量不止一个的物品拆成n个相同的物品(n是该物品的数量）。即如果一个物品的数量是n（n>1)，那么将其看成是n个物品，只不过他们的体积和价值都一样）

#include<iostream>

using namespace std;
const int N=2e6+10;;
int v[N],w[N],f[N];

int main()
{
    int n,m;
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int a,b,c,k=1;
        cin>>a>>b>>c;
        while(k<=c)
        {
            v[++cnt]=a;
            w[cnt]=b;
            k++;
        }
    }
    for(int i=1;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]<<endl;
    return 0;
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

经过实测，两者的运行时间貌似差不多

终极优化（二进制优化）

我们发现这个代码运行的还是很慢，时间复杂度是$O(n^3)$,这让人难以接受，聪明的你就想办法，想啊想，终于你灵光一现，发现了一种优化方法。

思路

对于上面的思考，虽然可以把多重背包问题拆成01背包问题，但是一个一个数的去拆解太慢了，聪明的你想到每一个数都可以用二进制来表示，所以我们可以把每个物品的数量n拆解成一些数(a1,a2,a3...at)，而这些数的组合可以表示1-n中的任意一个数。

我们以11为例，我们把11拆解成1,2,4,4这四个数，我们可以发现1-11中的任意一个数都可以用这些数的组合来表示。

那么我们怎么拆解才能得到这些数呢

        int a,b,c,k=1;
        cin>>a>>b>>c;
        while(k<=c)
        {
            v[++cnt]=k*a;
            w[cnt]=k*b;
            c-=k;
            k*=2;
        }
        if(c)
        {
            v[++cnt]=c*a;
            w[cnt]=c*b;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

**至于为什么可以这么拆解，以及这样拆解为什么一定对，相关的数学证明我就不写了，写了也没人看。 **

代码

#include<iostream>

using namespace std;
const int N=2e6+10;;
int v[N],w[N],f[N],cnt[N];

int main()
{
    int n,m;
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int a,b,c,k=1;
        cin>>a>>b>>c;
        while(k<=c)
        {
            v[++cnt]=k*a;
            w[cnt]=k*b;
            c-=k;
            k*=2;
        }
        if(c)
        {
            v[++cnt]=c*a;
            w[cnt]=c*b;
        }
    }
    for(int i=1;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]<<endl;
    return 0;
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

写在最后

如果你觉得我写题解还不错的，请各位王子公主移步到我的其他题解看看
数据结构与算法部分（还在更新中）：

• C++ STL总结 - 基于算法竞赛（强力推荐）
  • 最短路算法——Dijkstra（C++实现）
  • 最短路算法———Bellman_Ford算法（C++实现）
  • 最短路算法———SPFA算法（C++实现）
  • 最小生成树算法———prim算法（C++实现）
  • 最小生成树算法———Kruskal算法（C++实现）
  • 染色法判断二分图（C++实现）
  • 动态规划——01背包问题
  • 动态规划——完全背包问题

2. Linux部分（还在更新中）：

• Linux学习之初识Linux
• Linux学习之命令行基础操作

✨

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/82841