没有价值的背包

Question

我面临下一个问题，我有一个这样的 python 字典：

total = 30

companies = {
 'a': 30,
 'b': 7,
 'c': 21,
 'd': 5,
 'e': 5,
  etc
}

我想做的是以数字加起来为总数的方式对公司进行分组。在这个例子中，我想要的输出是：

group1 = {
 'a':30 
} 

group2 = {
 'c': 21,
 'b': 7
}

group3 = {
 'd': 5,
 'e': 5
}

如果字典中某个键的值 > 总计，则将创建一个仅包含该键的组 key:value。例如，如果我们有

companies = {
 'a': 30,
 'b': 7,
 'c': 21,
 'd': 5,
 'e': 5,
 'f': 32
 etc

}

group1 = {
 'f':32
}
etc

我已经搜索了各种实现方法，我发现最好的方法是 Knapsack，但该算法将仅作为输入权重、值作为 int。我还发现了这个有趣的模块：

https://developers.google.com/optimization/bin/knapsack

from __future__ import print_function
from ortools.algorithms import pywrapknapsack_solver

def main():
      # Create the solver.
      solver = pywrapknapsack_solver.KnapsackSolver(
      pywrapknapsack_solver.KnapsackSolver.
      KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER,
      'test')

      weights = [[565, 406, 194, 130, 435, 367, 230, 315, 393,
          125, 670, 892, 600, 293, 712, 147, 421, 255]]
      capacities = [850]
      values = weights[0]
      solver.Init(values, weights, capacities)
      computed_value = solver.Solve()

      packed_items = [x for x in range(0, len(weights[0]))
                if solver.BestSolutionContains(x)]
      packed_weights = [weights[0][i] for i in packed_items]

      print("Packed items: ", packed_items)
      print("Packed weights: ", packed_weights)
      print("Total weight (same as total value): ", computed_value)
if __name__ == '__main__':
      main()

我试图修改此算法以使用字典（尤其是字符串）但没有成功。

有没有更好的方法可以达到这个效果？

谢谢，

Answer 1

如果我对你的问题的理解是正确的，那么你希望将你创建的组的总数减到最少。这可以通过迭代地创建一个在每次迭代中具有尽可能多的权重的组然后解决剩余的项目来解决。

请注意，我使用了一个简单的递归实现来解决子集求和问题。如果您对更大的数据集进行操作，您可能希望使用更优化的框架。

# Group items into groups with max_weight
# Items with weight > max_weight get their own group
def create_groups(max_weight, items):
    # Will hold the assignment of each company to a group
    cur_group = 1
    groups = {}

    # Assign all companies with weight > max_weight
    for item, weight in items.items():
        if weight > max_weight:
            groups[item] = cur_group
            cur_group += 1

    # Cluster remaining items
    while 1:
        rem_items = {k: v for k, v in items.items() if not k in groups.keys()}
        if len(rem_items) == 0: break
        solution = solve_subset_sum(max_weight, rem_items)
        groups.update({k: cur_group for k in solution})
        cur_group += 1

    return groups


# Solve a subset sum problem 
def solve_subset_sum(max_weight, items):
    best_solution = []
    best_sum = 0
    for item, weight in items.items():
        if weight > max_weight: continue
        items_reduced = {k: v for k, v in items.items() if k != item}
        solution = solve_subset_sum(max_weight - weight, items_reduced)
        solution.append(item)
        solution_sum = sum([v for k, v in items.items() if k in solution])
        if solution_sum > best_sum:
            best_solution = solution
            best_sum = solution_sum

    return best_solution


if __name__ == '__main__':
    # Input as specified by you
    total = 30
    companies = {
        'a': 30,
        'b': 7,
        'c': 21,
        'd': 5,
        'e': 5,
        'f': 32
    }

    # Test it
    groups = create_groups(total, companies)
    print(groups)

代码的结果是 {'f': 1, 'a': 2, 'c': 3, 'b': 3, 'e': 4, 'd': 4}。格式为 item_name: group_number.

没有价值的背包

knapsack with no values

knapsack-problem

dynamic-programming

python-3.x