遍历对象的条件性组合

Question

我正在做一个小的营养计划，想找到一些食物的最佳组合，以满足热量和大量营养素方面的一些要求。就这个问题而言，我只关注目标卡路里。你知道吗

我有一个API的数据，它可以告诉我一种食物的情况。例如：

egg = Food(FOOD_IDS["Boiled Egg"])
print(egg.macros.__dict__)

结果：

{'protein_grams': 6.0, 'fat_grams': 4.5, 'carb_grams': 1.0, 'calories': 68.5}

我想做的是找到我现有食物的可能组合，这些组合能增加目标数量的卡路里。你知道吗

因此，如果我有egg，rice，chicken在一个foods的集合中，我怎么能找到这些食物的所有可能的组合，比如3000卡路里？你知道吗

我想用random来不断地把食物收集在while的循环中，直到达到卡路里的目标，但是随着我的食物清单的增长，我担心性能。我以前使用过product、combinations和permutations库中的itertools，但我不知道这些方法如何在这里应用，因为我打算在边界条件内迭代。你知道吗

以下是我迄今为止的尝试：

def get_daily_food_options(self):
    target = 3000
    food_combinations = []
    groceries = []
    groceries.append(Food(FOOD_IDS["Boiled Egg"]))
    groceries.append(Food(FOOD_IDS["Brown Rice"]))
    groceries.append(Food(FOOD_IDS["Chicken Breast"]))
    num_iterations = 100 # I have to manually change this to get more/less results
    for i in range(num_iterations):
        temp_combination = []
        current_calories = 0
        while current_calories < target:
            food = choice(groceries) # random (not smart)
            temp_combination.append(food)
            current_calories += food.macros.calories
        food_combinations.append(temp_combination)
    return food_combinations

这很有效。。。但是有没有更聪明的方法呢？你知道吗

为了简单起见，您可以使用这些int卡路里值进行测试： 蛋=68.5 大米=169.5 鸡肉=114.5

以下是我的程序的一些示例输出，以显示我是如何消化结果的：

Mixed Nuts (28.0g per serving) : 3 servings
Good Seed bread (28.0g per serving) : 2 servings
Brown Rice (45.0g per serving) : 1 servings
Pineapple (77.0g per serving) : 5 servings
Sweet Potato (120.0g per serving) : 4 servings
Boiled Egg (45.0g per serving) : 2 servings
Green Peas (89.0g per serving) : 5 servings
Salmon (113.0g per serving) : 7 servings
Chicken Breast (112.0g per serving) : 3 servings
Spinach (85.0g per serving) : 1 servings

Answer 1

下面的程序将获取总热量计数和一个整数列表，这些整数表示各个食物的热量含量。它试图找到那些食物的倍数，这些食物加起来正好等于所需的总热量：

from itertools import product

def get_combinations(total_calories, calorie_counts):
    n = len(calorie_counts)
    max_factors = [total_calories // calorie_counts[i] for i in range(n)]
    for t in product(*(range(factors + 1) for factors in max_factors)):
        calorie_count = sum([t[i] * calorie_counts[i] for i in range(n)])
        if calorie_count == total_calories:
            print(t)


get_combinations(3000, [300, 150, 200])

如果你坚持每种食物至少有一份，那么将for循环改为：

for t in product(*(range(1, factors + 1) for factors in max_factors)):

这个想法是，如果总热量是X，而一种食物是Y卡路里，那么该食物的唯一可能份数在[0..X//Y]范围内（或者[1..X//Y]，如果你坚持至少有一份）。因此，如果有N种食物，程序会通过生成长度为N的元组来对所有可能的食物组合进行详尽的试验，其中每个元组是一种可能的组合。你知道吗

See demo

Answer 2

通常类似里程表的方法是

def combos(menu,target,extra):  # menu: list of values
  # Put the biggest first for efficiency
  # and to avoid large shortfalls:
  order=sorted(enumerate(menu),key=lambda e: -e[1])
  # Construct inverse permutation:
  inv=[None]*len(menu)
  for i,(j,_) in enumerate(order): inv[j]=i
  for c in combos0([v for _,v in order],target,extra,[]):
    yield [c[i] for i in inv]
def combos0(menu,target,extra,pfx):
  v=menu[len(pfx)]
  # Leave no budget unspent:
  if len(pfx)==len(menu)-1:
    n=-(-target//v)  # ceiling division
    if target+extra>=n*v: yield pfx+[n]
  else:
    for i in range((target+extra)//v+1):
      for c in combos0(menu,target-i*v,extra,pfx+[i]): yield c

你的电话是combos([f.macros.calories for f in foods],3000,100)。你知道吗