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

文章目录

• 什么是多重背包问题？
• • 多重背包问题的数学模型
• 例题
• • 多重背包问题Ⅰ
  • 多重背包问题Ⅱ
• 总结

什么是多重背包问题？

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

在解决这个问题时，通常使用动态规划或贪心算法，具体取决于问题的约束条件。
在日常生活中，我们常常面临选择的困扰，如何在有限的资源下最大化收益？多重背包问题正是这种选择的数学模型。具体而言，给定一个背包的容量 C C C 和 n n n 种物品，每种物品 i i i 具有重量 w w w 和价值 v v v，而且可以选择多个单位。我们的目标是最大化总价值，同时不超过背包的容量。

多重背包问题的数学模型

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

max ⁡ ∑ i = 1 n v i ⋅ x i \max \sum_{i=1}^{n} v_i \cdot x_i maxi=1∑n​vi​⋅xi​

其中， x i x_i xi​ 表示选择物品 i i i 的数量，满足以下约束条件：

∑ i = 1 n w i ⋅ x i ≤ C \sum_{i=1}^{n} w_i \cdot x_i \leq C i=1∑n​wi​⋅xi​≤C

x i ∈ Z ≥ 0 x_i \in \mathbb{Z}_{\geq 0} xi​∈Z≥0​

接下来会展示几道例题。

例题

多重背包问题Ⅰ

问题：

输出格式和数据范围：

样例输出和输入：

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

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

d p [ j ] = m a x ( d p [ j ] , d p [ j − v [ i ] ] + w [ i ] ) dp[j] = max(dp[j], dp[j - v[i]] + w[i]) dp[j]=max(dp[j],dp[j−v[i]]+w[i])

其中， d p [ j ] dp[j] dp[j]表示容量为 j j j时的最大价值。

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

d p [ j ] = m a x ( d p [ j ] , d p [ j − v [ i ] ] + w [ i ] , d p [ j − 2 v [ i ] ] + 2 w [ i ] , … , d p [ j − n v [ i ] ] + n w [ i ] ) dp[j] = max(dp[j], dp[j - v[i]] + w[i], dp[j - 2v[i]] + 2w[i], \dots, dp[j - nv[i]] + nw[i]) dp[j]=max(dp[j],dp[j−v[i]]+w[i],dp[j−2v[i]]+2w[i],…,dp[j−nv[i]]+nw[i])

这个公式的解释是，针对每个容量 j j j，我们考虑物品 i i i 的不同数量，找到一个最优的数量组合，使得价值最大化。

解释：

1. 当选择 0 个物品 i i i 时，价值为 d p [ j ] dp[j] dp[j]。
2. 当选择 1 个物品 i i i 时，价值为 d p [ j − v [ i ] ] + w [ i ] dp[j - v[i]] + w[i] dp[j−v[i]]+w[i]。
3. 当选择 2 个物品 i i i时，价值为 d p [ j − 2 v [ i ] ] + 2 w [ i ] dp[j - 2v[i]] + 2w[i] dp[j−2v[i]]+2w[i]。
4. 依此类推，直到选择最多 n n n个物品 i i i。

因此，针对每个容量 ( j )，我们计算每种数量下的最大值，并更新 d p [ j ] dp[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 ∗ 1 0 9 4*10^9 4∗109，用刚才那种算法是会超时的。

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

原因与解释：

1. 二进制拆分：

   • 每个物品的数量可以被表示为一系列 2 的幂次方之和。这是因为任何正整数都可以通过二进制表示来拆分成若干个 1、2、4、8 等的组合。例如，数字 7 可以拆分为 (1 + 2 + 4)。
   • 对于 8 这个例子，你可以将其拆分为 (8) 或者 (4 + 4)（视情况而定）。这个方法将减少需要考虑的物品种类，使得后续的背包问题更容易处理。

2. 减少物品种类：

   • 通过将物品的数量拆分为 2 的幂次方，我们实际上减少了在解决背包问题时所需考虑的物品数量。例如，7 个物品可以看作 1 个物品（1 个）、1 个物品（2 个）和 1 个物品（4 个），而不是直接处理 7 个物品。
   • 这使得问题转变为多个 0-1 背包问题，每个物品的“虚拟”数量在其对应的 0-1 背包问题中被考虑。

3. 独立处理剩余物品：

   • 如果在拆分后有剩余的物品（例如在处理 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;
}

总结

在本文中，我们深入探讨了多重背包问题的动态规划解法及其优化策略。通过将物品的数量拆分为 2 的幂次方之和，我们成功地将复杂的多重背包问题转换为多个简单的 0-1 背包问题，从而降低了计算复杂度，提高了算法的效率。此外，结合具体实例和详细的代码实现，使得这一理论变得更为实用。

多重背包问题不仅在计算机科学中有着重要的应用，还在现实生活中为资源分配、库存管理等问题提供了有效的解决方案。掌握这一算法思路，可以为解决更复杂的组合优化问题奠定基础。

希望通过本篇文章，读者能够更好地理解多重背包问题，并在实际编程中灵活运用这些优化策略。