基于优化理论的子集均值均衡分配策略

from statistics import mean
import pulp

def solve_set_partitioning(superset_data, set_sizes_data):
    """
    使用PuLP解决集合划分问题，使子集均值接近超集均值。

    Args:
        superset_data (list): 超集中的元素列表。
        set_sizes_data (list): 每个子集所需的元素数量列表。

    Returns:
        tuple: (list of lists, list of floats) 分配后的子集列表及其均值。
    """
    superset = superset_data
    set_sizes = set_sizes_data
    N = len(set_sizes)

    # 验证输入
    if sum(set_sizes) != len(superset):
        raise ValueError("所有子集大小之和必须等于超集元素总数。")

    superset_mean = mean(superset)

    # 创建问题实例
    set_partitioning_model = pulp.LpProblem("Set_Partitioning_Model", pulp.LpMinimize)

    # 1. 定义决策变量
    # covering[s][i] 是一个二进制变量，如果超集中的第i个元素被分配给子集s，则为1，否则为0。
    covering = {}
    for s in range(N):
        vals = []
        for i, v in enumerate(superset):
            vals.append(
                pulp.LpVariable(
                    f"assign_s{s}_idx{i:02}_val{v}",
                    lowBound=0,
                    upBound=1,
                    cat=pulp.LpInteger,
                )
            )
        covering[s] = vals

    # 定义表示每个子集总和误差的变量
    abs_sum_errs = []
    for s_i in range(N):
        set_sum_err_abs = pulp.LpVariable(f"set_{s_i}_sum_error_abs", lowBound=0)
        abs_sum_errs.append(set_sum_err_abs)

    # 2. 定义目标函数
    # 最小化所有子集总和与目标总和的绝对误差之和。
    # 目标总和 = 子集大小 * 超集均值
    set_partitioning_model += pulp.lpSum(abs_sum_errs), "Minimize_Absolute_Sum_Errors"

    # 3. 添加约束
    for s_i, st_vars in covering.items():
        # 计算当前子集s_i的实际元素值之和
        current_set_sum = pulp.lpSum([p * superset[idx] for idx, p in enumerate(st_vars)])

        # 计算子集s_i的目标总和
        target_set_sum = set_sizes[s_i] * superset_mean

        # 定义子集s_i的总和误差 (实际总和 - 目标总和)
        set_sum_err = pulp.LpVariable(f"set_{s_i}_sum_error")
        set_partitioning_model += set_sum_err == (current_set_sum - target_set_sum), \
                                  f"Sum_Error_Definition_Set_{s_i}"

        # 将绝对误差转换为线性约束: |x| <= y 等价于 x <= y 和 -x <= y
        set_partitioning_model += abs_sum_errs[s_i] >= set_sum_err, \
                                  f"Abs_Error_Constraint_Pos_Set_{s_i}"
        set_partitioning_model += abs_sum_errs[s_i] >= -set_sum_err, \
                                  f"Abs_Error_Constraint_Neg_Set_{s_i}"

    # 约束: 每个子集的大小必须符合预设
    for n, st_vars in zip(set_sizes, covering.values()):
        set_partitioning_model += pulp.lpSum(st_vars) == n, \
                                  f"Set_Size_Constraint_{n}"

    # 约束: 超集中的每个元素只能被使用一次
    # 遍历超集中的每个元素（通过其索引），确保它在所有子集变量中总和为1
    for idx_in_superset in range(len(superset)):
        # 获取所有子集对应此元素的变量
        element_assignment_vars = [covering[s][idx_in_superset] for s in range(N)]
        set_partitioning_model += (
            pulp.lpSum(element_assignment_vars) == 1,
            f"Element_{idx_in_superset}_Used_Once",
        )

    # 4. 求解模型
    set_partitioning_model.solve()

    # 5. 解析结果
    if set_partitioning_model.status != pulp.LpStatusOptimal:
        print(f"求解状态: {pulp.LpStatus[set_partitioning_model.status]}")
        return [], []

    allocated_subsets = []
    subset_means = []
    for k, v in covering.items():
        current_subset = []
        for idx, var in enumerate(v):
            if var.value() == 1:
                current_subset.append(superset[idx])
        allocated_subsets.append(current_subset)
        if current_subset:
            subset_means.append(mean(current_subset))
        else:
            subset_means.append(0) # 或根据实际情况处理空子集

    return allocated_subsets, subset_means, superset_mean

# 示例1：完美分配
print("--- 示例1：完美分配 ---")
superset_ex1 = [100]*5 + [101]*10 + [102]*5
set_sizes_ex1 = [2, 4, 14]
subsets_ex1, means_ex1, total_mean_ex1 = solve_set_partitioning(superset_ex1, set_sizes_ex1)
print(f"超集均值: {total_mean_ex1}")
for i, subset in enumerate(subsets_ex1):
    print(f"子集 {i}: {subset}, 均值: {means_ex1[i]}")

# 示例2：最佳近似分配
print("\n--- 示例2：最佳近似分配 ---")
superset_ex2 = [100]*5 + [103]*10 + [104]*5
set_sizes_ex2 = [2, 4, 14]
subsets_ex2, means_ex2, total_mean_ex2 = solve_set_partitioning(superset_ex2, set_sizes_ex2)
print(f"超集均值: {total_mean_ex2}")
for i, subset in enumerate(subsets_ex2):
    print(f"子集 {i}: {subset}, 均值: {means_ex2[i]}")

--- 示例1：完美分配 ---
超集均值: 101.0
子集 0: [101, 101], 均值: 101.0
子集 1: [100, 100, 102, 102], 均值: 101.0
子集 2: [100, 100, 100, 101, 101, 101, 101, 101, 101, 101, 101, 102, 102, 102], 均值: 101.0

--- 示例2：最佳近似分配 ---
超集均值: 102.5
子集 0: [103, 103], 均值: 103.0
子集 1: [100, 100, 104, 104], 均值: 102.0
子集 2: [100, 100, 100, 103, 103, 103, 103, 103, 103, 103, 103, 104, 104, 104], 均值: 102.57142857142857

from statistics import mean
from numberpartitioning import karmarkar_karp

# 示例2数据
superset_ex2 = [100]*5 + [103]*10 + [104]*5

print("--- Karmarkar-Karp 算法示例 ---")
print("超集均值:", mean(superset_ex2))

# 将超集划分为3个子集
# 注意：karmarkar_karp不保证子集大小，只平衡子集和
partitions = karmarkar_karp(superset_ex2, num_parts=3).partition

for i, p in enumerate(partitions):
    print(f"子集 {i}: {p}, 均值: {mean(p)}, 大小: {len(p)}")

--- Karmarkar-Karp 算法示例 ---
超集均值: 102.5
子集 0: [104, 104, 103, 103, 103, 100], 均值: 102.83333333333333, 大小: 6
子集 1: [100, 103, 104, 103, 103, 103, 100], 均值: 102.28571428571429, 大小: 7
子集 2: [100, 104, 104, 103, 103, 103, 100], 均值: 102.42857142857143, 大小: 7