这是使用线性编程通过纸浆（https://pypi.org/project/PuLP）的解决方案，为我提供了最佳解决方案
Maximum energy level: 758.0Mapping of stores per foodtype: {1: [9, 2, 4], 0: [3, 8, 0, 6, 7], 2: [1, 5]}我认为该性能应优于手动编码的穷举求解器。
from collections import defaultdictimport pulp# datanStores = 10a, b, c = max_stores = 5, 3, 2matrix = [ [56, 44, 41], [56, 84, 45], [40, 98, 49], [91, 59, 73], [69, 94, 42], [81, 64, 80], [55, 76, 26], [63, 24, 22], [81, 60, 44], [52, 95, 11]]# create an LP problemlp = pulp.LpProblem("maximize energy", sense=pulp.LpMaximize)# create the list of indices for the variables# the variables are binary variables for each combination of store and food_type# the variable alpha[(store, food_typeà] = 1 if the food_type is taken from the storeindex = {(store, food_type) for store in range(nStores) for food_type in range(3)}alpha = pulp.LpVariable.dicts("alpha", index, lowBound=0, cat="Binary")# add the constrain on max storesfor food_type, n_store_food_type in enumerate(max_stores): lp += sum(alpha[(store, food_type)] for store in range(nStores)) <= n_store_food_type# only one food type can be taken per storefor store in range(nStores): lp += sum(alpha[(store, food_type)] for food_type in range(3)) <= 1# add the objective to maximiselp += sum(alpha[(store, food_type)] * matrix[store][food_type] for store, food_type in index)# solve the problemlp.solve()# collect the resultsstores_for_foodtype = defaultdict(list)for (store, food_type) in index: # check if the variable is active if alpha[(store, food_type)].varValue: stores_for_foodtype[food_type].append(store)print(f"Maximum energy level: {lp.objective.value()}")print(f"Mapping of stores per foodtype: {dict(stores_for_foodtype)}")
