大理石分桶最大化颜色共享：NP难证明与算法求解

问题描述 #

给定M颗大理石、B个桶，每个桶容量为K（满足M=BK）。已知各颜色的大理石数量（数组形式，总和为M），需找到一种分配方案，最大化颜色共享对数——不同颜色的唯一组合只要在同一个桶中出现过一次，就计为1次，最终统计所有此类唯一组合的总数。

评分函数的Python实现如下：

def score(aBuckets):
    seenPairs = set()
    for myBucket in aBuckets:
        for colourA in myBucket:
            for colourB in myBucket:
                if colourA != colourB:
                    seenPairs.add((colourA, colourB))
    return len(seenPairs)//2

NP难证明 #

通过归约自**集合覆盖问题（Set Cover，已知NP难）**可证明本问题的NP难性：

1. 问题转换：
   • 集合覆盖问题中，全集U含n个元素，m个子集S₁~Sₘ，目标是用最少子集覆盖U。
   • 对应到本问题：
     • 每个元素对应一种颜色，共n种颜色，每种颜色仅1颗大理石（颜色数组为n个1）。
     • 每个子集Sᵢ对应一个桶，桶容量K=|Sᵢ|，总桶数B=m，总大理石数M=Σ|Sᵢ|=n（满足M=BK）。
   • 本问题最大化颜色共享对数，等价于最大化出现在同一桶中的元素对数量，这与集合覆盖的目标高度相关：用更少的桶（子集）覆盖更多元素对，对应集合覆盖的最优解。
2. 归约正确性：
   • 若集合覆盖有最优解（t个子集覆盖U），则本问题用对应t个桶分配所有大理石，能得到最大共享对数（因每种颜色仅1颗，只能用这些桶）。反之，若本问题找到最大共享对数的分配，对应的桶集合即为集合覆盖的最优解。
   • 因此，本问题至少与集合覆盖问题难度相当，属于NP难问题。

算法方案 #

1. 贪心近似算法（高效且性能优异） #

核心逻辑：让高频颜色尽可能与更多其他颜色配对，同时最大化每个桶的颜色多样性。
步骤：

• 将颜色按数量从大到小排序（设颜色为c₁~cₙ，对应数量count₁≥count₂≥…≥countₙ）。
• 初始化B个空桶，每个桶跟踪当前包含的颜色集合和元素数量。
• 依次处理每颗大理石：
  • 对颜色cᵢ的每颗大理石，选择未包含cᵢ且已含颜色种类最少的桶（若有多个，选元素数量最少的），将大理石放入该桶。
  • 此策略能让高频颜色接触更多不同颜色，避免桶内重复颜色浪费容量，最大化新增颜色对的可能性。

2. K=2时的最优算法 #

当每个桶容量K=2时，问题等价于构建无向图：节点为颜色，边代表颜色对出现在同一桶中，目标是最大化边数，同时每个颜色cᵢ的度数不超过其大理石数量countᵢ。此时可通过优先给高频颜色匹配更多不同颜色的扩展最大匹配算法，得到最优解。

示例说明 #

给定M=8，B=4，K=2，颜色数组[2,2,2,2]（颜色A、B、C、D各2颗）：
原分配方案：

得分仅为2（仅(A,C)、(B,D)两对）。

优化后方案（交换桶1的C与桶2的D）：

得分提升至4（包含(A,C)、(A,D)、(B,C)、(B,D)四对），为最优解。

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