🌹作者:云小逸
📝個人主頁:云小逸的主頁
📝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 _{i=1}^s{v}_i)$。

一維多重背包

對于一維多重背包問題，我們可以使用動態規劃來解決。設 $dp[i][j]$ 表示前 $i$ 個物品中，容量為 $j$ 的背包所能裝下的最大價值。則有以下狀態轉移方程：

d p [ i ] [ j ] = max ? { d p [ i ? 1 ] [ j ? k ? w i ] + k ? v i } ( 0 ≤ k ≤ ? j w i ? ) dp[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) dp[i][j]=max{dp[i?1][j?k?wi?]+k?vi?}(0≤k≤?wi?j??)

其中 $w_i$ 表示第 $i$ 個物品的重量，$v_i$ 表示第 $i$ 個物品的價值。這個方程的意思是，我們可以選擇第 $i$ 個物品的 $k$ 個，然后再加上前 $i?1$ 個物品在剩余容量 $j?k?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 _{i=1}^s{v}_i)$。

優化版本

以上兩種方法的時間復雜度都比較高，無法通過本題。我們需要對其進行優化。

觀察上面的狀態轉移方程，我們可以發現其中有一個 $\max$ 函數，這個函數是比較耗時的。我們可以使用單調隊列來優化這個 $\max$ 函數。具體來說，我們可以將 $dp[i?1][j?k?w_i]+k?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);}}
}

時間復雜度為 $O(nm\log s)$。

---

最后

十分感謝你可以耐著性子把它讀完和我可以堅持寫到這里，送幾句話，對你，也對我：

1. 努力讀書，尤其是家境普通或者家境差的，去學習，你的目標就是改變自己的命運，駱家輝三代人才進白宮，英國印度裔首相蘇納克，三代人才進白金漢宮，所以有一代人必須做出付出，沒辦法，你的最大任務就是完成原始資本積累。

2.不要被別人牽著鼻子走，不要別人說什么就信什么，學會分辨是非。

3.不要隨便把情緒寫在臉上，冷靜不代表軟弱，理智不等于認慫。

4.我們不能一邊過著糟糕的生活，一邊期待好事發生在我們身上。

5.窮不沾色，富不沾賭。

?

最后如果覺得我寫的還不錯，請不要忘記點贊?，收藏?，加關注?哦(｡･ω･｡)

愿我們一起加油，奔向更美好的未來，愿我們從懵懵懂懂的一枚菜鳥逐漸成為大佬。加油，為自己點贊！
?

?