【算法】----多重背包问题I,II（动态规划）

🌹作者:云小逸
📝个人主页:云小逸的主页
📝Github:云小逸的Github
🤟motto:要敢于一个人默默的面对自己，强大自己才是核心。不要等到什么都没有了，才下定决心去做。种一颗树，最好的时间是十年前，其次就是现在！学会自己和解，与过去和解，努力爱自己。==希望春天来之前，我们一起面朝大海，春暖花开！==🤟
👏专栏：C++👏 👏专栏：Java语言👏👏专栏：Linux学习👏
👏专栏：C语言初阶👏👏专栏：数据结构👏👏专栏：备战蓝桥杯👏

文章目录

前言
多重背包问题
- 二维多重背包
- 一维多重背包
- 优化版本
最后

前言

今天我们接着上一篇博客继续学习背包问题：多重背包问题，这里将介绍完全背包问题的二维解法和一维解法以及优化版本，希望你可以喜欢。在这里插入图片描述 ——————————————————————————————

多重背包问题

多重背包问题是背包问题的一个变种。在这个问题中，每个物品有一个重量和一个价值，且可重复选择多次。背包有一个容量限制，问怎样选择物品可以使得背包中的总价值最大。

二维多重背包

对于二维多重背包问题，我们可以将其转化为一维多重背包问题来解决。具体来说，我们可以将第 $i$ 个物品拆成 $s_i$ 个物品，每个物品的重量和价值都是原来的 $\frac{w_i}{s_i}$ 和 $\frac{v_i}{s_i}$ 。这样就将二维多重背包问题转化为了一维多重背包问题。

代码实现如下：

int dp[N];
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= w[i]; j--) {
        for (int k = 1; k <= s[i] && k * w[i] <= j; k++) {
            dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);
        }
    }
}

时间复杂度为 $O(nm\sum\limits_{i=1}^s v_i)$ 。

一维多重背包

对于一维多重背包问题，我们可以使用动态规划来解决。设 $d p [i] [j]$ 表示前 $i$ 个物品中，容量为 $j$ 的背包所能装下的最大价值。则有以下状态转移方程：

$\max\{dp[i-1][j-k\cdot w_i]+k\cdot v_i\} \quad (0\leq k\leq \lfloor\frac{j}{w_i}\rfloor)$

其中 $w_i$ 表示第 $i$ 个物品的重量， $v_i$ 表示第 $i$ 个物品的价值。这个方程的意思是，我们可以选择第 $i$ 个物品的 $k$ 个，然后再加上前 $i - 1$ 个物品在剩余容量 $j-k\cdot w_i$ 的情况下所能取得的最大价值。

代码实现如下：

int dp[N];
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= w[i]; j--) {
        for (int k = 1; k * w[i] <= j && k <= s[i]; k++) {
            dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);
        }
    }
}

时间复杂度为 $O(nm\sum\limits_{i=1}^s v_i)$ 。

优化版本

以上两种方法的时间复杂度都比较高，无法通过本题。我们需要对其进行优化。

观察上面的状态转移方程，我们可以发现其中有一个 $\max$ 函数，这个函数是比较耗时的。我们可以使用单调队列来优化这个 $\max$ 函数。具体来说，我们可以将 $dp[i-1][j-k\cdot w_i]+k\cdot v_i$ 放入一个单调队列中，然后取队首元素即可。

代码实现如下：

int dp[N];
deque<int> q;
for (int i = 1; i <= n; i++) {
    for (int j = 0; j < w[i]; j++) {
        q.clear();
        for (int k = 0; k * w[i] + j <= m; k++) {
            int x = k * w[i] + j;
            if (!q.empty() && k - q.front() > s[i]) {
                q.pop_front();
            }
            if (!q.empty()) {
                dp[x] = max(dp[x], dp[x - w[i]] + k * v[i]);
                while (!q.empty() && dp[x - w[i]] - q.back() * v[i] >= 0) {
                    q.pop_back();
                }
            }
            q.push_back(k);
        }
    }
}