如何实现getMinCost函数？覆盖所有标签的最小成本求解

你的问题本质是经典的集合覆盖问题，这是一个NP-hard问题——贪心算法（每次选成本最低的问题）只能给出近似解，无法保证得到全局最优，所以会在部分测试用例中失效。比如下面这个场景：

假设有3个标签，问题1成本5，能覆盖所有3个标签；问题2、3、4成本各3，分别覆盖标签1、2、3。贪心会优先选成本低的2、3、4，总成本9，但最优解是选问题1，成本仅5。

要得到精确的最小成本，当标签数量较少（比如≤20）时，用状态压缩动态规划是最可行的方案，具体实现思路如下：

核心思路 #

用二进制数表示标签的覆盖状态：

• 一个m位的二进制数mask，第j位为1表示第j个标签已被覆盖，0表示未覆盖。
• 定义dp[mask]为覆盖mask对应标签集合所需的最小成本。

步骤 #

1. 初始化状态：dp[0] = 0（覆盖0个标签的成本为0），其余状态初始化为无穷大。
2. 遍历每个问题：先将当前问题的标签集合转换为二进制mask_i（比如问题i覆盖标签0和2，mask_i就是101即十进制5）。
3. 状态转移：对每个已有的状态mask，计算加入当前问题后的新状态new_mask = mask | mask_i，更新dp[new_mask] = min(dp[new_mask], dp[mask] + cost[i])。
4. 获取结果：最终dp[(1<<m)-1]就是覆盖所有标签的最小成本（(1<<m)-1是所有位都为1的二进制数，代表所有标签都被覆盖）。

代码实现示例 #

def getMinCost(cost, tagList):
    if not tagList:
        return 0
    m = len(tagList[0])  # 标签总数
    full_mask = (1 << m) - 1
    dp = [float('inf')] * (1 << m)
    dp[0] = 0
    
    for idx in range(len(cost)):
        # 生成当前问题的标签掩码
        current_mask = 0
        for tag_idx in range(m):
            if tagList[idx][tag_idx] == 1:
                current_mask |= (1 << tag_idx)
        # 更新所有可能的状态
        for mask in range(1 << m):
            if dp[mask] != float('inf'):
                new_mask = mask | current_mask
                if dp[new_mask] > dp[mask] + cost[idx]:
                    dp[new_mask] = dp[mask] + cost[idx]
    
    # 如果无法覆盖所有标签，返回-1（可根据需求调整）
    return dp[full_mask] if dp[full_mask] != float('inf') else -1

特殊情况处理 #

如果标签数量很大（比如m>20），2^m的状态数会爆炸（比如m=30时超过10亿），此时状态压缩DP不再适用。这种情况下可以考虑：

• 优化贪心策略：每次选择单位新增标签成本最低的问题（即（当前成本）/（新增标签数）最小），比单纯选成本最低的贪心效果更好，但仍为近似解。
• 启发式算法：比如分支定界、遗传算法等，在可接受时间内逼近最优解。

内容的提问来源于stack exchange，提问作者Sachin Kumar