1)题目意思
有 M 种口味(编号 1 到 M)。现在给你 N 包糖果,每包有 K 颗,输入会告诉你这一包里每颗糖的口味(同一包里口味可能重复)。
小明要买一些包,使得买到的所有包里出现过的口味种类能覆盖 1..M 全部口味。
要求输出:
* 最少买几包能覆盖全部口味
* 如果无论怎么买都覆盖不了,输出 -1
范围:N<=100,M<=20,K<=20。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2)思路解析(状态压缩 DP)
因为 M<=20,可以用一个二进制 mask 表示“已经覆盖了哪些口味”。
* mask 的第 i 位为 1 表示口味 i+1 已经品尝到
* 目标是得到 FULL = (1<<M)-1
先把每一包糖转换成一个 bagMask:
* 读入这包的 K 个口味 t
* 把对应的位设为 1(重复口味不会影响)
然后做最短步数 DP:
* dp[mask] 表示达到覆盖集合 mask 的最少包数
* 初始:dp[0]=0
* 转移:对每一包 bagMask,从 mask 到 mask | bagMask
dp[mask | bagMask] = min(dp[mask | bagMask], dp[mask] + 1)
最后看 dp[FULL]:
* 若还是无穷大,输出 -1
* 否则输出它
复杂度:
* 状态数 2^M 最大约 1,048,576
* N 最大 100
* 总体大约 N * 2^M,可以接受(常见做法)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3)代码
倒序枚举 mask 的原因是:保证每一包糖最多只被使用一次(0/1 选择)。
1)如果正序枚举会发生什么问题?
假设你正序写:
那么当你更新出一个新的状态 mask2 = mask|b 之后,因为是正序,后面循环可能马上又遇到 mask2,又会再用同一包 b 去更新一次,相当于允许:
* 同一包糖被买多次(变成“完全背包”/可重复选)
这就不符合题意(每包只有一包,买不买是 0/1)。
2)倒序为什么能避免重复使用?
倒序写:
因为你从大到小扫:
* 当你用 dp[mask] 去更新 dp[mask|b] 时,mask|b 一定 大于等于 mask
* 而倒序遍历时,mask|b 对应的位置已经在前面(更大)遍历过了,不会再被当作“本轮的来源状态”继续往后更新
* 所以这一轮(处理这一包)里,每个状态最多只会“用这包一次”,符合 0/1 选择
3)一句话总结
* 正序:会把同一包当成“可以买无限次”(错误)
* 倒序:保证同一包只用一次(正确)