当前位置：首页 > news >正文

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

news 来源：原创 2024/9/27 19:04:45

文章目录

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

在这里插入图片描述

什么是多重背包问题？

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

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

多重背包问题的数学模型

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

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

其中， $x_i$ 表示选择物品 $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 背包问题中，每个物品只能选择一次，因此状态转移方程是：

$d p [j] = ma x (d p [j], d p [j - v [i]] + w [i])$

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

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

$\dots, dp[j - nv[i]] + nw[i])$

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

解释：

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

因此，针对每个容量 ( j )，我们计算每种数量下的最大值，并更新 $d p [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;
}