[数据结构与算法]蓝桥杯-糖果（python，dfs，状态压缩和动态规划）

一、题目

题目 2302: 蓝桥杯2019年第十届省赛真题-糖果
时间限制: 1Sec 内存限制: 128MB 提交: 1502 解决: 432
题目描述
糖果店的老板一共有 M 种口味的糖果出售。为了方便描述，我们将 M 种 口味编号 1 ～ M。

小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而 是 K 颗一包整包出售。

幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知 道每包内的糖果口味。

给定 N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖 果。

输入
第一行包含三个整数 N、M 和 K。

接下来 N 行每行 K 这整数 T1, T2, · · · , TK，代表一包糖果的口味

(对于 30% 的评测用例，1 ≤ N ≤ 20 。

对于所有评测样例，1 ≤ N ≤ 100，1 ≤ M ≤ 20，1 ≤ K ≤ 20，1 ≤ Ti ≤ M 。)

输出
一个整数表示答案。如果小明无法品尝所有口味，输出 ?1。

样例输入

6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2

样例输出

2

二、思路和代码

dfs用的搜索，状态压缩和动态规划参考大佬cpp题解但最终甚至分数更低。虽然如此，状态压缩还是学到了。

2.1 bfs+小根堆+状态压缩（60）

import heapq

N, M, K = [int(x) for x in input().split()]
ls = list()
ls.append([])
for _ in range(N):
    ls.append([int(x) for x in input().split()])

# bfs
queue = list()


# 返回压缩状态
def getState(pack):
    res = 0
    for x in pack:
        res = res | 1 << (x - 1)
    return res


# 将糖果包转化为压缩状态
for i in range(1, N + 1):
    ls[i] = getState(ls[i])


# 结点结构为[已尝糖果压缩状态， 下一糖果包， 已用糖果包数]
class Node:
    def __init__(self, x, y, z):
        self.data = [x, y, z]

    def __gt__(self, other):
        return self.data[2] > other.data[2]

    def __ge__(self, other):
        return self.data[2] >= other.data[2]

    def __lt__(self, other):
        return self.data[2] < other.data[2]

    def __le__(self, other):
        return self.data[2] <= other.data[2]


heapq.heappush(queue, Node(0, 1, 0))
destination = pow(2, M) - 1
res = 0
while len(queue) != 0:
    cur = heapq.heappop(queue)
    data = cur.data
    # 若下一个已经没了，删除
    if data[1] == N + 1:
        continue
    # 下一个零食包加入
    data1 = data[0] | ls[data[1]]
    # 到达结果，退出
    if data1 == destination:
        res = data[2]
        break
    tempnode = Node(data1, data[1] + 1, data[2] + 1)
    heapq.heappush(queue, tempnode)
    # 下一个零食包不加入
    tempnode = Node(data[0], data[1] + 1, data[2])
    heapq.heappush(queue, tempnode)

if len(queue) == 0:
    print(-1)
else:
    print(res)

2.2dfs（40）

dfs（40分）：

N, M, K = [int(x) for x in input().split()]
ls = list()
# 插入头结点，为了下标一致
ls.append([])
for _ in range(N):
    ls.append([int(x) for x in input().split()])

# used记录第i包糖果是否买过，tasted记录已经尝过的味道，res记录最优包数
havntused = [i for i in range(N+1)]
tasted = [0 for _ in range(M+1)]
res = float("inf")


# 深度优先搜索，packs记录当前买了多少包
def dfs(packs):
    global res, tasted
    # 剪枝
    if packs >= res:
        return
    # 尝遍
    if sum(tasted) == M:
        res = min(res, packs)
        return
    if len(havntused) == 1:
        return
    # 遍历所有糖果包, 这个地方可以用一个链表数据结构存未买的糖果包（看看别人是怎么做的）
    for i in range(1, len(havntused)):
        # tasted0备份tasted, pack是这次要用的糖果包
        tasted0 = tasted[:]
        pack = havntused.pop(i)
        # 更新尝过的口味，这个地方先放着
        for x in ls[pack]:
            tasted[x] = 1
        dfs(packs+1)
        # 恢复
        havntused.insert(i, pack)
        tasted = tasted0


dfs(0)
if res == float("inf"):
    print(-1)
else:
    print(res)

2.3状态压缩和dp（10分）

# 动态规划，dp[i]表示达到i状态需要的最少包数
# 动态数组下标表达的是状态，i状态的含义是：糖果的状态用一位可以表示，采用状态压缩作为dp数组下标, 设下标为j的糖果包的状态为f（j）
# 则状态转移方程为：dp[i|f(j)] = min(dp[i]+1, dp[i|f(j)])
# 更新顺序为从只需要一包，用一包的更新两包，用两包的更新三包。。。
N, M, K = [int(x) for x in input().split()]
ls = list()
for _ in range(N):
    ls.append([int(x) for x in input().split()])


# 返回压缩状态
def getState(pack):
    res = 0
    for x in pack:
        res = res | 1<<(x-1)
    return res
# 动态数组
dp = [float("inf") for _ in range(pow(2, M))]

# 初始化dp，并修改存糖果包的ls中直接存储state
for i in range(N):
    state = getState(ls[i])
    ls[i] = state
    dp[state] = 1


# 考虑用第k个零食包
for k in range(N):
    # 用第k个零食包更新每个状态
    for j in range(pow(2, M)):
        if dp[j] != float("inf"):
            dp[j|ls[k]] = min(dp[j]+1, dp[j|ls[k]])

if dp[pow(2, M)-1] == float("inf"):
    print(-1)
else:
    print(dp[pow(2, M)-1])