如何在Python中找到满足条件（最大和最小阈值）的所有可能的组合？

Question

给予

names = ["bread","peanut_butter","yogurt","coffe"]
calories = [150,400,100,75]

和阈值

max_calories = 500
min_calories = 250

我想得到所有可能的食物组合，比如：

bread + yogurt = 250
bread + yogurt + coffe = 350
peanut_butter + yogurt = 500
peanut_butter + coffe = 475
peanut_butter = 400

这就是我目前掌握的情况。我只通过def greedy和"bread + yogurt + coffe = 350"通过def gready2获得了"peanut_butter = 400"。但我不知道如何通过def gready2获得所有剩余的组合。你知道吗

class Food(object):
    def __init__(self, n, c):
        self.name = n
        self.calories = c
    def getCalories(self):
        return self.calories
    def __str__(self):
        return f"{self.name}: < {self.calories} >"

def buildMenu(names, calories):
    """names, calories lists of same length.
       name a list of strings
       calories lists of numbers
       returns list of Foods"""
    menu = []
    for i in range(len(calories)):
        menu.append(Food(names[i], calories[i]))
    return menu

def greedy(items, maxCost, minCost):
    #Assumes items a list
    itemsCopy = items
    result = []
    totalCost = 0.0
    for i in range(len(itemsCopy)):
        if (itemsCopy[i].getCalories()) <= maxCost: 
            if (itemsCopy[i].getCalories()) >= minCost:
                result.append(itemsCopy[i])
                totalCost += itemsCopy[i].getCalories()         
    return (result, totalCost)

def greedy2(items, maxCost, minCost):
    #Assumes items a list
    itemsCopy = items
    result = []
    totalCost = 0.0
    for i in range(len(itemsCopy)):
        if (totalCost+itemsCopy[i].getCalories()) <= maxCost: 
            result.append(itemsCopy[i])
            totalCost += itemsCopy[i].getCalories()          
    return (result, totalCost)

def testGreedy(items, constraint, constraint2):
    taken, val = greedy(items, constraint, constraint2)
    for item in taken:
        print('   ', item)
        print("    ------------------------------------")


def testGreedy2(items, constraint, constraint2):
    taken2, val2 = greedy2(items, constraint, constraint2)
    print("   Total value of items taken =", val2 )
    for item in taken2:
        print("  ", item)



def testGreedys(foods, maxUnits, minUnits):
    print('Allocating', maxUnits,
          'calories:')
    print("")
    testGreedy(foods, maxUnits, minUnits)
    testGreedy2(foods, maxUnits, minUnits)


names = ["bread","peanut_butter","yogurt","coffe"]
calories = [150,400,100,75]
foods = buildMenu(names, calories)
testGreedys(foods, 500, 250) 

上述代码的结果

Allocating 500 calories:

     peanut_butter: < 400 >
        ------------------------------------
       Total value of items taken = 325.0
       bread: < 150 >
       yogurt: < 100 >
       coffe: < 75 >

Answer 1

这里的问题

这里的问题是，你没有真正解析所有可能的成分组合。 你只是试图添加更多的成分，直到你达到最大的量或热量允许，但这将导致许多可能性，仍然没有探索。你知道吗

要生成所有长度的所有组合，我喜欢使用itertools包：

from itertools import combinations, chain

names = ["bread","peanut_butter","yogurt","coffe"]

allCombinations = chain(*(combinations(names, i) for i in range(len(names) + 1)))

for combi in allCombinations:
    print(combi)

你一定能从这里算出你的代码。请注意，这是对所有组合的详尽解析，可以有更有效的算法来最终实现您想要的。你知道吗

完整代码示例

为了完整起见，我提供了完整的Python代码，您可以使用这些代码找到所需的组合：

from itertools import combinations, chain

# Inputs
names = ["bread","peanut_butter","yogurt","coffe"]
calories = [150, 400, 100, 75]
max_calories = 500
min_calories = 250

# Build mapping from name to number of calories
namesToCalories = {key:value for key, value in zip(names, calories)}

result = []

# Parse all combinations
allCombinations = chain(*(combinations(names, i) for i in range(len(names) + 1)))
for combi in allCombinations:
    # Get calories for this combination
    caloriesForThisCombination = sum((namesToCalories[name] for name in combi))
    # Test for min/max
    if caloriesForThisCombination > min_calories and caloriesForThisCombination < max_calories:
        result += [combi]

print(result)