通天之分組背包

題目鏈接

題目描述

自 $01$ 背包問世之后，小 A 對此深感興趣。一天，小 A 去遠游，卻發現他的背包不同于 $01$ 背包，他的物品大致可分為 $k$ 組，每組中的物品相互沖突，現在，他想知道最大的利用價值是多少。

輸入格式

兩個數 $m,n$，表示一共有 $n$ 件物品，總重量為 $m$。

接下來 $n$ 行，每行 $3$ 個數 $a_i,b_i,c_i$，表示物品的重量，利用價值，所屬組數。

輸出格式

一個數，最大的利用價值。

輸入輸出樣例 #1

輸入 #1

45 3
10 10 1
10 5 1
50 400 2

輸出 #1

10

說明/提示

$0\le m\le 1000$，$1\le n\le 1000$，$1\le k\le 100$，$a_i,b_i,c_i$ 在 int 范圍內。

\

0、分組背包特點

• 每組內只能選 一個物品 或者 不選任何物品；
• 每組之間是獨立的，可以按順序處理；
• 對每組分別進行一次 0-1 背包更新；
• 最終使用動態規劃來記錄狀態。

題解（二維dp）

---

一、狀態定義

我們使用二維動態規劃數組：

dp[i][j] 表示從前 i 個物品組中，在總容量恰好為 j 的情況下所能獲得的最大價值。

---

二、 初始化分析

for(ll j=0;j<=m;j++)
{dp[0][j]=0;
}

• 第 0 組表示“沒有物品可選”，此時無論容量是多少，最大價值都為 0；
• 其他位置初始化為 LLONG_MIN，表示不可達狀態。

---

三、狀態轉移方程

對于當前組中的每一個物品 {w, v}（重量和價值），我們嘗試將其加入到容量 j 的背包中：

if (j >= w) 
{dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v);
}

這個狀態轉移的意思是：

• 如果當前容量 j 可以裝下當前物品，則從上一組的容量 j - w 狀態中轉移過來，并加上該物品的價值；
• 否則保持不變（繼承上一組的狀態）。

---

四、實現細節

1.數據結構說明

map<ll, vector<pair<ll, ll>>> groups;

• 使用 map 來將物品按組號分類；
• 每個組是一個 vector<pair<weight, value>>，存儲該組中的所有物品。

2.動態規劃數組初始化

vector<vector<ll>> dp(group_count + 1, vector<ll>(m + 1, LLONG_MIN));
for(ll j=0;j<=m;j++)
{dp[0][j]=0;
}

• 初始時，除了第 0 組外，其他所有狀態設為最小值 LLONG_MIN；
• 第 0 組初始化為全 0，表示不選任何物品時的價值。

3.遍歷過程的主次順序

3.1. 外層循環：遍歷物品組

• 主要任務：遍歷每一個物品組（從第1組開始，跳過第0組）。
• 實現方式：

  for (auto it = (++groups.begin()); it != groups.end(); it++) 
  {ll gid = it->first;const vector<pair<ll, ll>>& items = it->second;// ...
  }
  

• 說明：這里的 it 是指向當前物品組的迭代器，gid 是當前組的組號，items 是該組內所有物品的集合。

3.2. 繼承上一組的狀態

• 主要任務：在處理當前組之前，首先繼承前一組的狀態（即假設不選擇當前組中的任何物品）。
• 實現方式：

  for (ll j = 0; j <= m; j++) 
  {dp[gid][j] = dp[gid - 1][j];
  }
  

• 說明：這一步確保了即使當前組沒有合適的物品可選或者我們決定不選當前組的任何物品時，我們的解不會變差。

3.3. 中層循環：遍歷當前組內的每個物品

• 主要任務：對于當前組中的每一個物品，嘗試將其加入背包，并更新相應的狀態。
• 實現方式：

  for (const auto& item : items) {ll w = item.first;  // 當前物品的重量ll v = item.second; // 當前物品的價值// ...
  }
  

3.4. 最內層循環：遍歷背包容量

• 主要任務：對于當前物品，遍歷所有可能的背包容量 j，并根據當前物品的重量和價值更新 dp 數組。
• 實現方式：

  for (ll j = w; j <= m; j++) 
  { // 注意這里從 w 開始循環if (dp[gid - 1][j - w] != LLONG_MIN){dp[gid][j] = max(dp[gid][j], dp[gid - 1][j - w] + v);}
  }
  

• 說明：這里從 w 開始循環是因為只有當背包容量大于等于當前物品的重量時，才有可能將該物品放入背包。

3.5.總結遍歷過程的主次順序

1. 外層循環：遍歷物品組

   • 對于每一個物品組（從第1組開始），獲取該組的所有物品。

2. 繼承上一組的狀態

   • 在處理當前組之前，先繼承前一組的狀態（即假設不選擇當前組中的任何物品），確保基礎狀態正確。

3. 中層循環：遍歷當前組內的每個物品

   • 對于當前組中的每一個物品，計算其對背包的影響。

4. 最內層循環：遍歷背包容量

   • 對于當前物品，遍歷所有可能的背包容量，并根據當前物品的重量和價值更新 dp 數組。

五、完整代碼

#include <bits/stdc++.h>
using namespace std;
using ll = long long;int main() 
{// m 表示背包的最大容量// n 表示物品總數ll m, n;cin >> m >> n;// 使用 map 將物品按組號分類存儲// groups[group_id] 存儲該組下的所有物品 {weight, value}map<ll, vector<pair<ll, ll>>> groups;// 插入一個無效的第0組，使后續組號可以直接和 dp 數組下標對應groups[0].push_back({0, 0});// 輸入每個物品的信息：重量、價值、所屬組號for (ll i = 0; i < n; i++) {ll weight, value, group_id;cin >> weight >> value >> group_id;groups[group_id].push_back({weight, value});}// 動態規劃數組 dp[i][j]// dp[i][j] 表示前 i 組物品，在容量 j 下可以獲得的最大價值// 初始化為 LLONG_MIN 表示不可達狀態ll group_count = groups.size() - 1; // 減去人為添加的第0組vector<vector<ll>> dp(group_count + 1, vector<ll>(m + 1, LLONG_MIN));// 初始狀態：前 0 組（沒有選任何物品）時，所有容量下的最大價值都是 0for (ll j = 0; j <= m; j++) {dp[0][j] = 0;}// 遍歷每一組（從實際的第1組開始）// 注意這里使用 ++groups.begin() 跳過第0組for (auto it = (++groups.begin()); it != groups.end(); it++) {ll gid = it->first;                     // 當前組號const vector<pair<ll, ll>>& items = it->second; // 該組的所有物品// 先繼承上一組的狀態（不選當前組中的任何物品）for (ll j = 0; j <= m; j++) {dp[gid][j] = dp[gid - 1][j];}// 對當前組中的每一個物品嘗試選擇for (const auto& item : items) {ll w = item.first;   // 當前物品的重量ll v = item.second;  // 當前物品的價值// 遍歷所有可能的背包容量 j，從當前物品的重量開始for (ll j = w; j <= m; j++) {// 如果上一組 j - w 容量是可達的，則更新當前組 j 容量下的最大價值if (dp[gid - 1][j - w] != LLONG_MIN) {dp[gid][j] = max(dp[gid][j], dp[gid - 1][j - w] + v);}}}}// 輸出結果：最后一組在最大容量 m 下所能獲得的最大價值cout << dp[group_count][m] << endl;return 0;
}

---

六、 時間與空間復雜度分析

類型	復雜度
時間復雜度	$O(G?m?K)$
空間復雜度	$O(G?m)$

其中：

• $G$：物品組數；
• $m$：背包容量；
• $K$：平均每組中的物品數量。

---

題解（滾動數組優化）

一、 動態規劃數組 dp[j]

• 定義：dp[j] 表示在容量為 j 的情況下可以獲得的最大價值。
• 初始化：所有值初始化為 LLONG_MIN（表示不可達狀態），除了 dp[0] = 0（容量為 0 時的最大價值為 0）。

2. 遍歷主次順序

2.1主循環：遍歷每一組物品

for (auto it = groups.begin(); it != groups.end(); it++) 
{const vector<pair<ll, ll>>& items = it->second;

• 遍歷順序：我們首先遍歷每一個物品組，從第一個組到最后一個組依次處理。
• 原因：這樣可以確保每組的狀態轉移依賴于前一組的狀態，從而逐步構建最終的最優解。

2.2次循環：倒序處理容量 j

vector<ll> temp_dp(dp); // 先繼承上一組的狀態for (ll j = m; j >= 0; j--) 
{for (const auto& item : items) {ll weight = item.first;ll value = item.second;if (j >= weight && dp[j - weight] != LLONG_MIN) {temp_dp[j] = max(temp_dp[j], dp[j - weight] + value);}}
}

• 倒序處理容量 j：從大到小遍歷容量 j，確保每次更新不會覆蓋尚未使用的舊值。
• 原因：因為在動態規劃中，我們需要基于未被當前操作修改過的舊值進行計算，倒序遍歷可以避免數據覆蓋的問題。

3. 使用臨時 dp 數組

vector<ll> temp_dp(dp); // 先繼承上一組的狀態

• 為什么需要臨時 dp 數組：

  • 在處理每一組時，我們需要先保存上一組的狀態（即假設不選擇當前組中的任何物品）。
  • 如果直接在 dp 上進行更新，會導致后續的操作基于已經被修改的狀態，從而影響結果的正確性。
  • 使用臨時數組 temp_dp 可以確保我們在處理當前組的所有物品之前，已經完整地保存了上一組的狀態。

• 合并 temp_dp 到 dp：

  • 在處理完當前組的所有物品之后，我們將 temp_dp 合并回 dp，以完成狀態轉移。

4. 輸出結果

cout << *max_element(dp.begin(), dp.end()) << endl;

• 輸出最大價值：由于我們的目標是找到最大可能的價值，而不是僅限于給定容量 m，所以我們使用 *max_element(dp.begin(), dp.end()) 來獲取整個 dp 數組中的最大值。

---

5.完整代碼

#include <bits/stdc++.h>
using namespace std;
using ll = long long;int main() 
{// 輸入 m 表示背包的最大容量// n 表示物品總數ll m, n; cin >> m >> n;// 使用 map 存儲每組物品：// group_id -> vector<pair<weight, value>> 表示每個組中的所有物品map<ll, vector<pair<ll, ll>>> groups;// 讀取每個物品的信息：重量、價值、所屬組號for (ll i = 0; i < n; i++) {ll weight, value, group_id;cin >> weight >> value >> group_id;groups[group_id].push_back(make_pair(weight, value));}// 動態規劃數組 dp[j]：// 表示當前狀態下，容量為 j 時可以獲得的最大價值// 初始值設為 LLONG_MIN 表示不可達的狀態// dp[0] 初始化為 0 表示容量為 0 時的價值為 0vector<ll> dp(m + 1, LLONG_MIN);dp[0] = 0;// 遍歷每一組物品for (auto it = groups.begin();it != groups.end(); ++it) {// 當前組的所有物品列表const vector<pair<ll, ll>>& items = it->second;// 創建 temp_dp 作為當前組的臨時狀態數組// temp_dp 初始化為當前 dp 的值（繼承上一組的狀態）// 這樣做是為了保證我們可以不選當前組中的任何物品vector<ll> temp_dp(dp);// 倒序遍歷容量 j（從大到小）// 原因：防止在更新 temp_dp[j] 時，前面已經計算過的結果被覆蓋for (ll j = m; j >= 0; j--) {// 嘗試從當前組中選擇每一個物品for (const auto& item : items) {ll weight = item.first;ll value = item.second;// 如果當前容量 j 足夠裝下這個物品，并且 j - weight 狀態可達if (j >= weight && dp[j - weight] != LLONG_MIN) {// 更新 temp_dp[j] 為：// 前一組容量 j - weight 的最大價值 + 當前物品價值// 取 max 是因為可能有多個物品競爭同一個 j 容量temp_dp[j] = max(temp_dp[j], dp[j - weight] + value);}}}// 將 temp_dp 合并回 dp 中，表示處理完這一組后的最終狀態dp = temp_dp;}// 輸出結果：整個 dp 數組中的最大值（不一定剛好用滿容量 m）cout << *max_element(dp.begin(), dp.end()) << endl;return 0;
}