求满足指定条件的唯一实体组合（按成本排序）

问题说明 #

需要找出所有合理的实体组合，满足以下要求：

• 组合需覆盖全部指定条件（允许条件重叠）
• 排除冗余组合（比如包含无意义额外实体的组合，如示例中的[E1, E3, E4, E7]，因为E7覆盖的E不是必需条件，且增加后无意义）
• 最终结果按组合总成本升序排序

示例 #

输入条件 #

Criteria: [A, B, C, D]
Entities: [
   E1 = (costs = 5, covers = [A, B, E]),
   E2 = (costs = 5, covers = [C, D]),
   E3 = (costs = 2, covers = [B, C]),
   E4 = (costs = 1, covers = [D]),
   E5 = (costs = 5, covers = [B, D]),
   E6 = (costs = 3, covers = [B, D]),
   E7 = (costs = 0, covers = [E])
]

预期输出（成本 → 组合） #

[
  (8, [E1, E3, E4]),
  (10, [E1, E2]),
  (10, [E1, E3, E6]),
  (12, [E1, E3, E5])
]

背景与现状 #

• 实际实体规模：0~20个，覆盖条件重叠较多
• 开发语言：Kotlin
• 当前尝试：用关键路径算法仅能找到最低成本方案，但需要获取所有合理可行方案，以便后续权衡其他非成本因素

实现思路（Kotlin） #

1. 生成所有可能的有效组合 #

因为实体数量最多20个，直接暴力枚举所有子集效率偏低，用回溯法+剪枝优化更合适：

• 先按实体成本升序排序，优先尝试低成本实体，提前剪枝掉成本已超过当前已知较高成本的分支
• 跟踪当前已覆盖的条件，当满足全部条件时，记录组合并停止该分支深入
• 跳过冗余实体：如果当前实体覆盖的条件已被现有组合完全覆盖，且成本不为0，直接跳过

2. 去重与筛选合理组合 #

• 去重：将实体按ID排序后存入集合，避免顺序不同但实体一致的重复组合
• 筛选冗余组合：如果从组合中移除任意一个实体后，仍能覆盖全部条件，则该组合属于冗余，直接排除

3. 排序 #

将最终筛选后的组合按总成本升序排列

代码示例片段 #

data class Entity(val id: String, val cost: Int, val covers: Set<String>)

fun findValidCombinations(criteria: Set<String>, entities: List<Entity>): List<Pair<Int, List<Entity>>> {
    val sortedEntities = entities.sortedBy { it.cost }
    val validCombos = mutableSetOf<List<Entity>>()

    fun backtrack(index: Int, currentCovers: MutableSet<String>, currentCombo: MutableList<Entity>) {
        // 已满足所有条件，检查是否为非冗余组合
        if (currentCovers.containsAll(criteria)) {
            val isNonRedundant = currentCombo.all { entity ->
                val tempCovers = currentCovers - entity.covers
                !tempCovers.containsAll(criteria)
            }
            if (isNonRedundant) {
                // 按ID排序后存入集合，避免顺序不同的重复组合
                validCombos.add(currentCombo.sortedBy { it.id })
            }
            return
        }
        // 遍历剩余实体并剪枝
        for (i in index until sortedEntities.size) {
            val entity = sortedEntities[i]
            // 剪枝：当前实体覆盖的条件已完全被覆盖且成本不为0，跳过
            if (currentCovers.containsAll(entity.covers) && entity.cost != 0) continue
            
            currentCovers.addAll(entity.covers)
            currentCombo.add(entity)
            backtrack(i + 1, currentCovers, currentCombo)
            // 回溯
            currentCombo.removeLast()
            currentCovers.removeAll(entity.covers)
        }
    }

    backtrack(0, mutableSetOf(), mutableListOf())

    // 转换为成本+组合的列表，按成本升序排序
    return validCombos.map { combo ->
        combo.sumOf { it.cost } to combo
    }.sortedBy { it.first }
}

// 测试调用
fun main() {
    val criteria = setOf("A", "B", "C", "D")
    val entities = listOf(
        Entity("E1", 5, setOf("A", "B", "E")),
        Entity("E2", 5, setOf("C", "D")),
        Entity("E3", 2, setOf("B", "C")),
        Entity("E4", 1, setOf("D")),
        Entity("E5", 5, setOf("B", "D")),
        Entity("E6", 3, setOf("B", "D")),
        Entity("E7", 0, setOf("E"))
    )

    val result = findValidCombinations(criteria, entities)
    result.forEach { (cost, combo) ->
        println("($cost, [${combo.joinToString { it.id }}])")
    }
}

代码说明 #

• 回溯法生成有效组合，通过剪枝减少不必要的计算
• 加入非冗余检查：确保组合中每个实体都是必要的，排除无意义的冗余组合
• 最终结果按总成本升序排列，组合内实体按ID排序保证一致性

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