【DP解密多重背包问题】：优化策略与实现

用户11305458

发布于 2024-10-09 17:27:18

1490

发布于 2024-10-09 17:27:18

文章被收录于专栏：学习

什么是多重背包问题？

多重背包问题是一个经典的组合优化问题。与标准背包问题不同，在多重背包问题中，每种物品可以选择多个，而不是只选择一次。具体来说，给定一个背包的容量和若干种物品，每种物品有一个重量和价值，目标是最大化在背包中放入的物品总价值，同时不超过背包的容量。

在解决这个问题时，通常使用动态规划或贪心算法，具体取决于问题的约束条件。在日常生活中，我们常常面临选择的困扰，如何在有限的资源下最大化收益？多重背包问题正是这种选择的数学模型。具体而言，给定一个背包的容量

和

种物品，每种物品

具有重量

和价值

，而且可以选择多个单位。我们的目标是最大化总价值，同时不超过背包的容量。

多重背包问题的数学模型

我们可以通过以下公式来表示多重背包问题：

\max \sum_{i=1}^{n} v_i \cdot x_i

其中，

x_i

表示选择物品

的数量，满足以下约束条件：

\sum_{i=1}^{n} w_i \cdot x_i \leq C

x_i \in \mathbb{Z}_{\geq 0}

接下来会展示几道例题。

例题

多重背包问题Ⅰ

问题：

输出格式和数据范围：

样例输出和输入：

算法原理： 相较于01背包问题来说，多重背包问题当中每个物品的个数不止是一个而是多个。相较于完全背包问题来说这些物品都不是无锡无限的。举个例子：

物品标号	1	2	3	4
单个物品容量	1	2	3	4
物品个数	3	1	3	2
单个物品价值	2	4	4	5

以上面这个为例子，假设背包的容量是5，可以选择的物品个数是4，我们该如何选择呢，按照01背包问题的思想：我们可以先创建一个dp数组，dp[i]表示物品容量是i时的最大价值。在 0-1 背包问题中，每个物品只能选择一次，因此状态转移方程是：

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

其中，

dp[j]

表示容量为

时的最大价值。

在多重背包问题中，每个物品有多个数量可以选择，因此状态转移方程变为：

dp[j] = max(dp[j], dp[j - v[i]] + w[i], dp[j - 2v[i]] + 2w[i], \dots, dp[j - nv[i]] + nw[i])

这个公式的解释是，针对每个容量

，我们考虑物品

的不同数量，找到一个最优的数量组合，使得价值最大化。

解释：

当选择 0 个物品

时，价值为

dp[j]

。

当选择 1 个物品

时，价值为

dp[j - v[i]] + w[i]

。

当选择 2 个物品

时，价值为

dp[j - 2v[i]] + 2w[i]

。

依此类推，直到选择最多

个物品

。

因此，针对每个容量 ( j )，我们计算每种数量下的最大值，并更新

dp[j]

。

所以我们需要一个循环来遍历每一种个数的情况：

代码展示：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int N,V;
    cin>>N>>V;
    vector<int> dp(V+1,0);
    for(int i=0;i<N;i++)
    {
        int vi,wi,si;
        cin>>vi>>wi>>si;
        for(int j=V;j>=vi;j--)
        {
            for(int k=1;k<=si&&j>=k*vi;k++)
            {
                dp[j]=max(dp[j],dp[j-k*vi]+k*wi);
            }
        }
    }
    cout<<dp[V]<<endl;
    return 0;
}

多重背包问题Ⅱ

问题：

数据范围：

输入样例和输出样例：

可以看见这道题的题目要求和上道题一模一样,但是数据范围发生了变化，我们先看看上道题的数据范围是100,100,100。套了三层循环顶多也就100万，对于C++来说100万是可以接受的，但是这道题的数据范围是1000,2000,2000，算出来是

4*10^9

，用刚才那种算法是会超时的。

算法优化： 假如某个物品有7个，我们是不是可以将这7个物品分为若干份，最容易想到的：七个物品我们可以分为7份，然后每个物品的物品数量也可以相应的划分，是不是可以转换为一个01背包问题，但是这里我们划分的份数是不是太多了，我们可以来简化一下，我是否可以将一个物品的数量划分为2的幂次方个之和，就拿上面的例子为例，7个物品，我们可以划分为：1+2+4,这里很巧合的是刚刚好划分完了，但是如果我们有8个物品呢？是不是最后还剩下一一个，这个不能划分为2的幂次方的我们单独讨论即可，我们将每个物品分好组之后然后进行一次01背包问题即可。在处理多重背包问题时，我们可以使用二进制拆分的方法来简化问题。

原因与解释：

二进制拆分：
- 每个物品的数量可以被表示为一系列 2 的幂次方之和。这是因为任何正整数都可以通过二进制表示来拆分成若干个 1、2、4、8 等的组合。例如，数字 7 可以拆分为 (1 + 2 + 4)。
- 对于 8 这个例子，你可以将其拆分为 (8) 或者 (4 + 4)（视情况而定）。这个方法将减少需要考虑的物品种类，使得后续的背包问题更容易处理。
减少物品种类：
- 通过将物品的数量拆分为 2 的幂次方，我们实际上减少了在解决背包问题时所需考虑的物品数量。例如，7 个物品可以看作 1 个物品（1 个）、1 个物品（2 个）和 1 个物品（4 个），而不是直接处理 7 个物品。
- 这使得问题转变为多个 0-1 背包问题，每个物品的“虚拟”数量在其对应的 0-1 背包问题中被考虑。
独立处理剩余物品：
- 如果在拆分后有剩余的物品（例如在处理 8 个物品时多出 1 个），可以单独将这一部分作为一个新的物品进行处理。这不会影响已经拆分的部分，因为已经处理的组合都是由 2 的幂构成的。

总结： 通过将物品数量拆分为 2 的幂次方之和，你可以有效地将多重背包问题转换为多个 0-1 背包问题，简化问题的复杂性，并且只需关注相对较少的物品组合。这个策略的有效性源于数学上对整数的分解性质，确保了每个可能的选择都能够被覆盖。

代码展示：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//大数据范围用二进制分解优化

const int V=2001;
int n,m;

struct Good
{
    //容量
    int v;
    //价值
    int w;
};

int main()
{
    vector<Good> good;
    vector<int> dp(V,0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int vi,wi,si;
        cin>>vi>>wi>>si;
        for(int k=1;k<=si;k*=2)
        {
            si-=k;
            good.push_back({k*vi,k*wi});
        }
        //有剩的，但是不能组成2的幂次方
        if(si>0)
            good.push_back({si*vi,si*wi});
    }
    //重新做一次01背包
    for(auto e:good)
    {
        for(int j=m;j>=e.v;j--)
        {
            dp[j]=max(dp[j],dp[j-e.v]+e.w);
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}