Python字典元素按目标值分组方案求助：适配Knapsack算法遇阻

嘿，你找对方向了——背包算法确实是解决这类分组问题的最优选择之一！你之前的困扰主要是怎么把字典的字符串键和背包算法的索引对应起来，我来给你梳理一个可行的实现方案：

首先，我们可以把问题拆成两步：

• 第一步：先处理所有值大于total的元素，直接单独为它们创建分组，这部分逻辑很简单。
• 第二步：对剩下的元素，循环使用背包算法找出能刚好凑成total的组合，每次找到一组就从剩余元素中移除，直到剩下的元素无法凑出total，就把它们作为最后一组。

下面是完整的代码实现，已经适配了字典的字符串键：

from ortools.algorithms import pywrapknapsack_solver

def group_companies(companies, total):
    groups = []
    
    # 先处理值超过total的元素，单独成组
    remaining_items = {}
    for company, value in companies.items():
        if value > total:
            groups.append({company: value})
        else:
            remaining_items[company] = value
    
    # 循环用背包算法凑组，直到剩余元素为空
    while remaining_items:
        # 提取剩余元素的键和值，方便背包算法处理
        company_keys = list(remaining_items.keys())
        values = list(remaining_items.values())
        # ortools的背包求解器要求weights是二维列表
        weights = [values]
        capacities = [total]
        
        # 初始化动态规划背包求解器
        solver = pywrapknapsack_solver.KnapsackSolver(
            pywrapknapsack_solver.KnapsackSolver.KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER,
            'CompanyGrouping'
        )
        solver.Init(values, weights, capacities)
        solver.Solve()
        
        # 获取选中元素的索引
        selected_indices = [i for i in range(len(values)) if solver.BestSolutionContains(i)]
        
        # 如果找不到能凑成total的组合，把剩下的元素全部作为一组
        if not selected_indices:
            groups.append(remaining_items.copy())
            break
        
        # 构建当前分组，并从剩余元素中移除这些项
        current_group = {company_keys[i]: values[i] for i in selected_indices}
        groups.append(current_group)
        
        # 更新剩余元素：保留未被选中的项
        remaining_items = {
            company_keys[i]: values[i] 
            for i in range(len(values)) 
            if i not in selected_indices
        }
    
    return groups

# 测试第一个示例
total = 30
companies_example1 = {
    'a': 30,
    'b': 7,
    'c': 21,
    'd': 5,
    'e': 5
}

result1 = group_companies(companies_example1, total)
for idx, group in enumerate(result1, 1):
    print(f"group{idx} = {group}")

# 测试第二个包含超大值的示例
companies_example2 = {
    'a': 30,
    'b': 7,
    'c': 21,
    'd': 5,
    'e': 5,
    'f': 32
}

print("\n第二个示例结果：")
result2 = group_companies(companies_example2, total)
for idx, group in enumerate(result2, 1):
    print(f"group{idx} = {group}")

代码解释： #

• 处理超大值元素：我们先遍历字典，把值大于total的元素直接加入结果组，剩下的元素存入remaining_items待处理。
• 背包算法适配字典：通过把字典的键和值分别存入列表company_keys和values，背包算法返回的选中索引就能直接映射回原来的公司键，完美解决了你之前遇到的字符串键处理问题。
• 循环凑组：每次用背包算法找到一组能凑成total的元素后，就从剩余元素中移除这些元素，重复这个过程直到剩余元素无法凑出total，就把它们全部作为最后一组。

这个实现对于中小规模的字典效率足够，如果你的字典元素数量非常大（比如上千个），可以考虑优化背包算法的类型或者加入一些剪枝逻辑，但一般业务场景下这个方案完全够用。

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