使用加法生成所有列表组合

Question

我有一个列表是这样的： ["Name/num1/num2/num3/num4/num5", ...]

例如： available = ["a/1/2/3/4/5", "b/5/4/3/2/4", "c/4/3/2/1/3"]

我试图在available中创建每个可能的项目组合，其中组合中每个项目的num5之和（例如for a is 5、for b is 1、for c is 5）小于MAXNUM（例如3000）。你知道吗

为了举例说明，程序将为上面的available和MAXNUM = 9创建一个生成器，可以转换为以下列表：

[["a/1/2/3/4/5", "b/5/4/3/2/4"], ["a/1/2/3/4/5", c/4/3/2/1/3], [b/5/4/3/2/4, b/5/4/3/2/4], [b/5/4/3/2/4, "c/4/3/2/1/3"], ["c/4/3/2/1/3", "c/4/3/2/1/3", "c/4/3/2/1/3"]]

注意：此代码需要返回一个结果，available有100个项目，并且MAXNUM = 3000在合理的时间内（理想情况下不超过10分钟）

编辑：以下是我的代码在实际使用中的要求：

import itertools
import sys
import time

sys.setrecursionlimit(10000000)

#["Name/Carbs/Protein/Fat/Vitamins/Calories"]
available = ['Fiddleheads/3/1/0/3/80', 'Fireweed Shoots/3/0/0/4/150', 'Prickly Pear Fruit/2/1/1/3/190', 'Huckleberries/2/0/0/6/80', 'Rice/7/1/0/0/90', 'Camas Bulb/1/2/5/0/120', 'Beans/1/4/3/0/120', 'Wheat/6/2/0/0/130', 'Crimini Mushrooms/3/3/1/1/200', 'Corn/5/2/0/1/230', 'Beet/3/1/1/3/230', 'Tomato/4/1/0/3/240', 'Raw Fish/0/3/7/0/200', 'Raw Meat/0/7/3/0/250', 'Tallow/0/0/8/0/200', 'Scrap Meat/0/5/5/0/50', 'Prepared Meat/0/4/6/0/600', 'Raw Roast/0/6/5/0/800', 'Raw Sausage/0/4/8/0/500', 'Raw Bacon/0/3/9/0/600', 'Prime Cut/0/9/4/0/600', 'Cereal Germ/5/0/7/3/20', 'Bean Paste/3/5/7/0/40', 'Flour/15/0/0/0/50', 'Sugar/15/0/0/0/50', 'Camas Paste/3/2/10/0/60', 'Cornmeal/9/3/3/0/60', 'Huckleberry Extract/0/0/0/15/60', 'Yeast/0/8/0/7/60', 'Oil/0/0/15/0/120', 'Infused Oil/0/0/12/3/120', 'Simple Syrup/12/0/3/0/400', 'Rice Sludge/10/1/0/2/450', 'Charred Beet/3/0/3/7/470', 'Camas Mash/1/2/9/1/500', 'Campfire Beans/1/9/3/0/500', 'Wilted Fiddleheads/4/1/0/8/500', 'Boiled Shoots/3/0/1/9/510', 'Charred Camas Bulb/2/3/7/1/510', 'Charred Tomato/8/1/0/4/510', 'Charred Corn/8/1/0/4/530', 'Charred Fish/0/9/4/0/550', 'Charred Meat/0/10/10/0/550', 'Wheat Porridge/10/4/0/10/510', 'Charred Sausage/0/11/15/0/500', 'Fried Tomatoes/12/3/9/2/560', 'Bannock/15/3/8/0/600', 'Fiddlehead Salad/6/6/0/14/970', 'Campfire Roast/0/16/12/0/1000', 'Campfire Stew/5/12/9/4/1200', 'Wild Stew/8/5/5/12/1200', 'Fruit Salad/8/2/2/10/900', 'Meat Stock/5/8/9/3/700', 'Vegetable Stock/11/1/2/11/700', 'Camas Bulb Bake/12/7/5/4/400', 'Flatbread/17/8/3/0/500', 'Huckleberry Muffin/10/5/4/11/450', 'Baked Meat/0/13/17/0/600', 'Baked Roast/4/13/8/7/900', 'Huckleberry Pie/9/5/4/16/1300', 'Meat Pie/7/11/11/5/1300', 'Basic Salad/13/6/6/13/800', 'Simmered Meat/6/18/13/5/900', 'Vegetable Medley/9/5/8/20/900', 'Vegetable Soup/12/4/7/19/1200', 'Crispy Bacon/0/18/26/0/600', 'Stuffed Turkey/9/16/12/7/1500']

global AllSP, AllNames
AllSP = []
AllNames = []

def findcombs(totalNames, totalCarbs, totalProtein, totalFat, totalVitamins, totalNutrients, totalCalories, MAXCALORIES):
    doneit = False
    for each in available:
        each = each.split("/")
        name = each[0]
        carbs = float(each[1])
        protein = float(each[2])
        fat = float(each[3])
        vitamins = float(each[4])
        nutrients = carbs+protein+fat+vitamins
        calories = float(each[5])
#        print(totalNames, totalCalories, calories, each)
        if sum(totalCalories)+calories <= MAXCALORIES:
            doneit = True
            totalNames2 = totalNames[::]
            totalCarbs2 = totalCarbs[::]
            totalProtein2 = totalProtein[::]
            totalFat2 = totalFat[::]
            totalVitamins2 = totalVitamins[::]
            totalCalories2 = totalCalories[::]
            totalNutrients2 = totalNutrients[::]

            totalNames2.append(name)
            totalCarbs2.append(carbs)
            totalProtein2.append(protein)
            totalFat2.append(fat)
            totalVitamins2.append(vitamins)
            totalCalories2.append(calories)
            totalNutrients2.append(nutrients)
#            print("    ", totalNames2, totalCarbs2, totalProtein2, totalFat2, totalVitamins2, totalNutrients2, totalCalories2)
            findcombs(totalNames2, totalCarbs2, totalProtein2, totalFat2, totalVitamins2, totalNutrients2, totalCalories2, MAXCALORIES)
        else:
            #find SP
            try:
                carbs    = sum([x * y for x, y in zip(totalCalories, totalCarbs)])    / sum(totalCalories)
                protein  = sum([x * y for x, y in zip(totalCalories, totalProtein)])  / sum(totalCalories)
                fat      = sum([x * y for x, y in zip(totalCalories, totalFat)])      / sum(totalCalories)
                vitamins = sum([x * y for x, y in zip(totalCalories, totalVitamins)]) / sum(totalCalories)
                balance  = (carbs+protein+fat+vitamins)/(2*max([carbs,protein,fat,vitamins]))
                thisSP   = sum([x * y for x, y in zip(totalCalories, totalNutrients)]) / sum(totalCalories) * balance + 12
            except:
                thisSP = 0
            #add SP and names to two lists
            AllSP.append(thisSP)
            AllNames.append(totalNames)

def main(MAXCALORIES):
    findcombs([], [], [], [], [], [], [], MAXCALORIES)
    index = AllSP.index(max(AllSP))
    print()
    print(AllSP[index], "  ", AllNames[index])

for i in range(100, 3000, 10):
    start = time.time()
    main(i)
    print("Calories:", i, ">>> Time:", time.time()-start)

Answer 1

对，因此N食物的任务具有O(exp(N))的时间和空间复杂性。你需要的是一些像A* (link)这样的启发式搜索，它遵循一个不完整的组合“有多好”的概念来指导它的进一步搜索。因此，您将在有限的时间内找到一个实用的好解决方案，而不是最佳解决方案。备选方案有遗传算法、模拟退火算法和其他优化算法。请注意，您必须定义一个衡量每个组合有多好的指标！你知道吗

我在我的电子游戏AI中使用了包astar（https://github.com/jrialland/python-astar），它超出了我的预期。你知道吗

进一步建议：使用namedtuple使代码更具可读性，否则您将讨厌发现bug并扩展它：

from collections import namedtuple

food = namedtuple('Food', 'name carbs protein fat vitamins calories')

bananas = food('bananas', 10, 15, 20, 10, 100)
oranges = food('oranges', carbs=10, protein=15, fat=20, vitamins=10, calories=100)
print(bananas.calories, oranges.fat)