餐饮计划算法？

Question

假设我有一个食物数据库，每种食物都有一定的脂肪、碳水化合物和蛋白质含量。比如说，我的数据库里有这些食物：

Item          Fat         Carbs         Protein
================================================
Milk           12           36             8
Chicken         1           12            18
Juice           0           50             2
Bacon           9            1             4

我想找一个有效的算法，看看这些食物的组合能否满足我想要的脂肪、碳水化合物和蛋白质的范围，而且每种食物可以用多次。

比如，如果我想要的组合在脂肪：20-30，碳水化合物：170-190，蛋白质：100-110的范围内，那么2杯牛奶、5只鸡、1杯果汁和0条培根就是一个可能的组合，0杯牛奶、5只鸡、2杯果汁和2条培根也是一个可能的组合。

如果算法在找到一个可能的解决方案后就停止，那也是可以的，但我希望这个算法不是确定性的，这样下次运行时可能会找到不同的解决方案。

这个问题听起来像是一个NP难题，比如子集和问题或背包问题，我查过这些算法，但对多约束问题的算法不太理解。而且背包问题是要优化，而这里并没有优化的需求。

我想如果数据库里的食物更多，这个问题会更难解决；如果解决方案不局限于整数（比如0.2杯牛奶），那找到一个符合条件的单一解决方案会简单得多。

我打算在Python中实现类似的功能，所以如果有Python的解决方案就太好了，谢谢。

Answer 1

如果现在数学编程对你来说太难了，可以先从一个叫做随机爬山算法的东西开始学习。

你描述的问题有点像混合问题。这里有一个我找到的MiniZinc解决方案（这是一个简单的例子）。

Answer 2

即使你只需要关注一种营养素（比如单独的蛋白质），你的问题也至少和允许重复的子集和问题一样复杂。因为无论你想要的范围是什么，你都可以把目标和乘以一个正整数，然后定义这个范围到下一个整数的前一个数。同样地，你也可以把你所有的数乘以同一个正整数再加1，这样你就能知道如果你能解决这个特定范围的问题，那么你就能解决子集和的问题。

你可以用整数线性规划来解决这个问题。你可以用一个变量Xi来表示你会包含多少个第i种物品，然后设置一些限制条件，比如

Fmin <= F1*X1 + F2*X2 + ... + Fn*Xn <= Fmax

这里的Fi是第一个物品中的脂肪含量，而[Fmin,Fmax]是你允许的脂肪范围。你还需要限制条件，确保每个Xi都大于等于0。整数线性规划会找到一个有效的Xi解，使得一个线性函数

C1*X1 + C2*X2 + ... + Cn*Xn

被最小化或最大化，其中的Ci是常数。通过改变Ci，你可以得到不同的有效解。获取所有有效解，甚至仅仅是计算有效解的数量，都是一个更复杂的问题。