在藍橋杯中遇到的這道題，看上去比較普通，但其實蘊含了很巧妙的“狀態壓縮 + 背包”的思想，本文將從零到一，詳細解析這個問題。

目錄

一、題目?

二、思路分析：狀態壓縮 + 最小覆蓋

1. 本質：最小集合覆蓋問題

2. 狀態設計：壓縮子集狀態

3. 狀態轉移邏輯

4. 為什么不用回溯解決？

三、狀壓DP通用壓縮和轉移技巧

1. 應用場景

2. 狀壓DP的核心構建思維

3. 狀態遍歷技巧

四、代碼

五、關鍵點總結

---

一、題目?

4.糖果 - 藍橋云課

?【翻譯過來就是】：

店里有 M 種不同口味的糖果。老板不單賣糖果，而是將 K 顆糖果打包成一包，并且每包糖果的口味可以預知。小明希望通過購買若干包糖果，品嘗到所有 M 種口味

我們的目標是：求出小明最少要買多少包糖果，才能嘗到所有口味？
若無論如何都無法湊齊所有口味，輸出 -1

二、思路分析：狀態壓縮 + 最小覆蓋

1. 本質：最小集合覆蓋問題

這道題本質上是一個最小集合覆蓋問題：

給定 M 個元素的全集，每個集合（糖果包）覆蓋部分元素，求用最少的集合數量，使得它們的并集恰好覆蓋全集。

這類問題是組合優化中非常典型的 NP 完全問題，而這道題因為數據規模小（M ≤ 20），我們可以用狀態壓縮優化搜索空間

2. 狀態設計：壓縮子集狀態

考慮全集是口味 {1, 2, ..., M}，那么每種“已經吃到的口味組合”可以表示為一個二進制串，長度為 M：

• 第 i 位為 1 表示第 i 種口味已吃；

• 第 i 位為 0 表示第 i 種口味未吃；

• 例如 01101 表示嘗到了第 0、2、3 種口味。

于是我們就可以設計出如下的狀態壓縮動態規劃：

• 狀態定義：dp[s] 表示要想吃到狀態 s 表示的口味集合，最少要買多少包糖果；

• 狀態個數：全集口味數為 M，所以一共有 2^M 個狀態；

• 初始狀態：dp[0] = 0 表示什么都沒吃；

• 最終目標：我們要找出 dp[full]，其中 full=(1<<M)-1，即全1，代表吃全所有口味

3. 狀態轉移邏輯

我們遍歷每一包糖果（相當于“可以選的物品”），如果當前狀態是 j，那么加入這一包糖果之后，會變成新狀態 j|a[i]

轉移公式如下：

dp[j|a[i]] = min(dp[j|a[i]], dp[j]+ 1)

意思是：“如果我當前吃到的是狀態j，現在加上這包糖果 a[i]，我就能達到一個新的狀態j |a[i]，那到達新狀態的最小糖果包數，可能是之前狀態的基礎上+1

為了避免狀態轉移時污染原始狀態（避免用新的 dp[j|a[i]]去影響其它轉移），我們從大到小遍歷狀態 j

4. 為什么不用回溯解決？

很多讀者第一時間可能想到回溯 + 剪枝，但那樣復雜度是指數級的

這題可以用動態規劃，是因為：

• 狀態可以表示為一個整數，并且狀態間的轉移有明顯結構；

• 每一步的選擇（糖果包）都可以使得狀態“合并”；

• 我們可以用子問題的最優解構造出大問題的最優解，符合DP的子結構性質。

三、狀壓DP通用壓縮和轉移技巧

狀態壓縮 DP是競賽算法中經常考的一種技巧，尤其當狀態具有“組合”性質時非常常見

1. 應用場景

• 集合覆蓋類問題（如本題）

• 旅行商問題（TSP）

• 開關燈問題 / 翻牌問題

• 博弈論中已訪問節點記錄

• 圖上路徑問題中“走過哪些點”狀態的保存

2. 狀壓DP的核心構建思維

1. 狀態壓縮：

   • 使用一個整數的二進制表示“某種集合”

   • 長度為 M 的集合有 2^M 個子集，對應 0~2^M - 1 這 2^M 個整數

2. 狀態定義：

   • 每一個狀態代表一種“中間形態”，可以是路徑、集合、排列的某種子結構

   • dp[mask] 表示從起點出發，達到狀態 mask 所需要的最小代價/方案數等

3. 狀態轉移：

   • 通常通過 dp[old_mask]->dp[new_mask] 來實現

   • new_mask=old_mask|(1<<x) 表示在old_mask 的基礎上加入一個新元素

   • 利用位運算快速合并和判斷狀態（如：是否包含、是否重疊等）

3. 狀態遍歷技巧

接下來給大家附上一下狀態壓縮常用的小技巧

遍歷目標	寫法
遍歷所有狀態	for (int mask = 0; mask < (1 << M); mask++)
遍歷 mask 的所有子集	for (int sub = mask; sub; sub = (sub - 1) & mask)
檢查 mask 是否包含第 i 項	if (mask & (1 << i))
加入元素 i	mask | (1 << i)
刪除元素 i	mask & ~(1 << i)

四、代碼

#include <iostream>
#include <cstring>
#include <algorithm> 
#include <climits>
using namespace std;
long long dp[(1<<20)+1];//左移20位
int n,m,k;
int a[110];//第i包所有的種類 
int main()
{fill(dp,dp+(1<<20)+1,INT_MAX);//初始化為最大值cin>>n>>m>>k;//n包糖果，m種口味，每包k種int c[25];//占位數組，是否能全部嘗到fill(c,c+m,0);bool no=false;//是否能全部嘗到//讀入n包糖果for(int i=1;i<=n;i++){int x=0,y;for(int j=1;j<=k;j++){cin>>y;//轉換為二進制//(1后面有y-1個0，相當于第y位是1） y--;x|=(1<<y); //先檢驗糖果是否全 //索引向后移一位 c[y]++;}a[i]=x;} //首先檢驗糖果種類是否齊全for(int i=0;i<m;i++){if(!c[i]) no=true;} if(no) cout<<"-1";else{//背包問題，裝i包糖果使每一種口味都能嘗到 dp[0]=0;//遍歷每一包 for(int i=1;i<=n;i++){//狀態從大到小 //背包問題，滾動數組背包容量從大到小 for(int j=(1<<m)-1;j>=0;j--){//是否選第i包 dp[j|a[i]]=min(dp[j|a[i]],dp[j]+1);}}//0-m-1位都為1 cout<<dp[(1<<m)-1];}return 0;
} 

五、關鍵點總結

技巧	說明
狀態壓縮	將口味組合轉換為一個整數表示
背包狀態轉移	dp[new_state] = min(dp[new_state], dp[old_state] + 1)
滾動數組優化	狀態轉移從大到小，避免重復選擇
初始化技巧	INT_MAX 代表當前狀態不可達，一定要用 long long 存儲，否則可能溢出

這個問題很好的考察了對“狀態壓縮 + 背包模型”的掌握，也是一道藍橋杯常考的“最小覆蓋子集”變形題，可以作為一道練手題

如果你覺得本文對你有幫助，歡迎點贊收藏！