选取固定大小物品子集以最小化标签最大出现次数问题

问题描述 #

需要从10000个物品中选取1000个，使得选中物品里出现次数最多的标签的频次尽可能最小。每个物品带有3个标签（取值为A-G），标签顺序无关，物品可能重复携带同一标签。

数据生成代码：

import random
import pandas as pd

def RandLet():    
    alphabet = "ABCDEFG"
    return alphabet[random.randint(0, len(alphabet) - 1)]

items = pd.DataFrame([{"ID": i, "Label1": RandLet(), "Label2": RandLet(), "Label3": RandLet()} for i in range(0, 10000)])

示例数据：

ID Label1 Label2 Label3
0   0      G      B      D
1   1      C      B      C
2   2      C      A      B

比如从这3个物品选2个时，选ID0和ID2更优：标签B出现2次（最大值），比选ID1和ID2的标签C出现3次的结果更好。

已有进展 #

已将原数据转换为7维度（对应A-G）的计数格式，每个维度记录物品对应标签的出现次数：

def ReshapeItems(items):
    alphabet = "ABCDEFG"
    item_rebuilder = []
    for _, row in items.iterrows():
        letter_counter = {letter: sum(row[[c for c in items.columns if "Label" in c]] == letter) for letter in alphabet}
        letter_counter["ID"] = row["ID"]
        item_rebuilder.append(letter_counter)
    return pd.DataFrame(item_rebuilder)

items2 = ReshapeItems(items)

转换后示例：

A  B  C  D  E  F  G  ID
0  0  1  0  1  0  0  1   0
1  0  1  2  0  0  0  0   1
2  1  1  1  0  0  0  0   2

当前瓶颈：常规背包问题是最大化价值同时约束体积，但此问题是固定选取数量（1000个），需要最小化各标签频次的最大值。

解决思路 #

核心思路：二分查找+可行性验证 #

这个问题可以转化为寻找最小的K值，使得存在1000个物品的子集，所有标签的总频次都不超过K。步骤如下：

1. 确定K的范围：最小可能的K是ceil(3*1000/7)≈429（1000个物品共3000个标签，平均分配到7个标签的理论值），最大可能的K是3*1000=3000（所有物品都带同一个标签）。
2. 二分查找K：对每个候选K，验证是否能选出1000个物品，使得每个标签的总计数≤K。
3. 可行性验证：用启发式贪心策略优先选择标签计数分布更均衡的物品，或者优先选择对当前高频标签贡献小的物品。

替代思路：迭代调整法 #

如果二分查找的验证逻辑过于复杂，可以用迭代优化的方法，实现简单且适合大数据量场景：

1. 随机选取1000个物品作为初始子集；
2. 计算当前子集各标签的频次，找到频次最高的标签L；
3. 在子集中找到携带L最多的物品X，在全集（非子集）中找到携带L最少的物品Y；
4. 用Y替换X，重新计算频次；
5. 重复步骤2-4，直到替换后无法降低最大频次，或达到迭代次数上限。

实现代码（迭代调整法） #

以下是基于迭代调整的实现，返回符合要求的物品子集：

import numpy as np

def select_optimal_subset(items2, subset_size=1000, max_iter=1000):
    # 初始化随机子集
    subset_indices = np.random.choice(len(items2), subset_size, replace=False)
    subset = items2.iloc[subset_indices].copy()
    # 获取标签列
    label_cols = [c for c in items2.columns if c != "ID"]
    
    for _ in range(max_iter):
        # 计算当前子集各标签的总频次
        total_counts = subset[label_cols].sum()
        max_label = total_counts.idxmax()
        current_max = total_counts.max()
        
        # 找到子集中带max_label最多的物品
        subset_max_items = subset[subset[max_label] == subset[max_label].max()]
        if len(subset_max_items) == 0:
            break
        item_to_replace = subset_max_items.sample(1).iloc[0]
        
        # 找到非子集中带max_label最少的物品（优先选带0的）
        non_subset = items2.drop(subset_indices)
        min_count = non_subset[max_label].min()
        candidate_items = non_subset[non_subset[max_label] == min_count]
        if len(candidate_items) == 0:
            break
        
        # 随机选一个候选替换
        replacement = candidate_items.sample(1).iloc[0]
        
        # 替换
        subset = subset.drop(item_to_replace.name)
        subset = pd.concat([subset, replacement.to_frame().T])
        subset_indices = subset.index
        
        # 检查是否有改进
        new_total = subset[label_cols].sum()
        new_max = new_total.max()
        if new_max >= current_max:
            # 替换没效果，退出
            break
    
    # 返回原始items中的对应行
    selected_ids = subset["ID"].tolist()
    return items[items["ID"].isin(selected_ids)]

代码说明 #

1. 初始随机选1000个物品，保证初始解的随机性；
2. 每次迭代找到当前最“坏”的物品（携带最高频次标签最多的），替换成最“好”的候选（携带该标签最少的）；
3. 当替换无法降低最大频次时停止，避免无效迭代；
4. 最终返回原始DataFrame中的选中行，方便后续使用。

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