【算法竞赛】状态压缩型背包问题经典应用（蓝桥杯2019A4分糖果）

在蓝桥杯中遇到的这道题，看上去比较普通，但其实蕴含了很巧妙的“状态压缩 + 背包”的思想，本文将从零到一，详细解析这个问题。

目录

一、题目 

二、思路分析：状态压缩 + 最小覆盖

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 存储，否则可能溢出

这个问题很好的考察了对“状态压缩 + 背包模型”的掌握，也是一道蓝桥杯常考的“最小覆盖子集”变形题，可以作为一道练手题

如果你觉得本文对你有帮助，欢迎点赞收藏！