擅长:python、mysql、java
<p>下面的程序将获取总热量计数和一个整数列表,这些整数表示各个食物的热量含量。它试图找到那些食物的倍数,这些食物加起来正好等于所需的总热量:</p>
<pre><code>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])
</code></pre>
<p>如果你坚持每种食物至少有一份,那么将for循环改为:</p>
<pre><code>for t in product(*(range(1, factors + 1) for factors in max_factors)):
</code></pre>
<p>这个想法是,如果总热量是X,而一种食物是Y卡路里,那么该食物的唯一可能份数在[0..X//Y]范围内(或者[1..X//Y],如果你坚持至少有一份)。因此,如果有N种食物,程序会通过生成长度为N的元组来对所有可能的食物组合进行详尽的试验,其中每个元组是一种可能的组合。你知道吗</p>
<p><a href="http://ideone.com/HrMKrW" rel="nofollow noreferrer">See demo</a></p>