指定组合的最小成本求解：现有算法存局限，求最优解法

问题定义 #

给定长度为n的cost数组，以及两个长度为n的集群兼容数组cluster1、cluster2（1表示兼容，0表示不兼容），需选择若干索引，满足：

• 选中索引中cluster1[i]=1的数量≥m
• 选中索引中cluster2[i]=1的数量≥m
  求满足条件的最小总成本，若无法满足则返回-1。

原方法的缺陷 #

优先选择同时兼容两个集群的元素，再补充各自集群的低成本元素的贪心策略，无法覆盖所有最优场景。比如示例2中，优先选高成本的共同兼容元素会导致总成本过高，而选择少量共同元素+足够的单集群低成本元素反而更优。

正确解法 #

步骤1：分类筛选与预处理 #

将所有元素按兼容情况分为三类，分别按成本升序排序，并计算前缀和数组（前缀和数组的第k项表示选前k个元素的总成本，pre[0]=0）：

• A类：cluster1[i]=1且cluster2[i]=1（同时兼容双集群）→ 排序后得到listA，前缀和preA
• B类：cluster1[i]=1且cluster2[i]=0（仅兼容集群1）→ 排序后得到listB，前缀和preB
• C类：cluster1[i]=0且cluster2[i]=1（仅兼容集群2）→ 排序后得到listC，前缀和preC

步骤2：边界可行性判断 #

先检查是否存在可行解：

• 集群1的总兼容数 = len(listA) + len(listB) ≥ m
• 集群2的总兼容数 = len(listA) + len(listC) ≥ m
  若任意一项不满足，直接返回-1。

步骤3：枚举共同兼容元素的选中数量 #

遍历所有可能的A类选中数量k，计算对应场景的总成本，取最小值：

• k的取值范围：k_min ≤ k ≤ k_max
  • k_min：max(0, m - len(listB), m - len(listC)) → 确保选k个A类后，剩余需要的单集群元素数量不超过对应类的总数
  • k_max：min(len(listA), m + len(listB) + len(listC)) → 选超过m个A类的场景也会被覆盖，但无需额外限制
• 对每个合法的k，计算需要补充的单集群元素数量：
  • 需补充B类数量：needB = max(0, m - k)
  • 需补充C类数量：needC = max(0, m - k)
• 对应总成本：preA[k] + preB[needB] + preC[needC]

步骤4：计算最小总成本 #

遍历所有合法的k，记录最小的总成本即可。

示例2验证 #

以示例2为例：

• listA：[30, 200] → preA = [0, 30, 230]
• listB：[3,4,6] → preB = [0,3,7,13]
• listC：[5,10] → preC = [0,5,15]
• m=3

边界条件：集群1总兼容数5≥3，集群2总兼容数4≥3，可行。
k_min = max(0, 3-3=0, 3-2=1) =1，k_max=min(2,3)=2

• 当k=1时：needB=2，needC=2，总成本=30+7+15=52（最优解）
• 当k=2时：needB=1，needC=1，总成本=230+3+5=238

因此最小成本为52，符合预期。

时间复杂度 #

• 分类排序：O(n log n)
• 前缀和计算：O(n)
• 枚举k：O(len(listA)) → 最坏O(n)，整体复杂度为O(n log n)，可处理n=2×10^5的场景。

代码示例（Python） #

def min_total_cost(cost, cluster1, cluster2, m):
    # 分类筛选元素
    A = []
    B = []
    C = []
    for c, c1, c2 in zip(cost, cluster1, cluster2):
        if c1 == 1 and c2 == 1:
            A.append(c)
        elif c1 == 1:
            B.append(c)
        elif c2 == 1:
            C.append(c)
    
    # 按成本升序排序
    A.sort()
    B.sort()
    C.sort()
    
    # 生成前缀和数组
    def get_prefix_sum(arr):
        prefix = [0]
        total = 0
        for num in arr:
            total += num
            prefix.append(total)
        return prefix
    
    preA = get_prefix_sum(A)
    preB = get_prefix_sum(B)
    preC = get_prefix_sum(C)
    
    # 检查是否存在可行解
    total_c1 = len(A) + len(B)
    total_c2 = len(A) + len(C)
    if total_c1 < m or total_c2 < m:
        return -1
    
    min_cost = float('inf')
    lenA, lenB, lenC = len(A), len(B), len(C)
    
    # 枚举所有合法的k值
    k_min = max(0, m - lenB, m - lenC)
    k_max = min(lenA, m + lenB + lenC)
    
    for k in range(k_min, k_max + 1):
        needB = max(0, m - k)
        needC = max(0, m - k)
        # 确保有足够的元素可选
        if needB > lenB or needC > lenC:
            continue
        current_cost = preA[k] + preB[needB] + preC[needC]
        if current_cost < min_cost:
            min_cost = current_cost
    
    return min_cost if min_cost != float('inf') else -1

# 示例1测试
cost1 = [3,4,5,6,3,2,10]
c1_1 = [1,1,0,1,1,1,0]
c2_1 = [0,0,1,0,1,1,0]
m1 = 3
print(min_total_cost(cost1, c1_1, c2_1, m1))  # 输出13

# 示例2测试
cost2 = [3,4,5,6,30,200,10]
c1_2 = [1,1,0,1,1,1,0]
c2_2 = [0,0,1,0,1,1,1]
m2 = 3
print(min_total_cost(cost2, c1_2, c2_2, m2))  # 输出52

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