用餐计划算法？

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

即使你只有一种营养素（例如单独的蛋白质）需要担心，你的问题至少和允许重复的子集总和一样困难，因为无论你希望你的范围是什么，你都可以将目标总和乘以正整数倍，然后定义到下一个倍数减1的范围，类似地将你集合的所有数字乘以相同的正整数，再加上1，如果你能用一个特定的范围解决你的问题，你就能得到你能解决的子集和。

你可以使用整数线性规划来解决你的问题，让变量席表示你将包含多少个项目，然后有约束。

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

其中Fi是第1项中的脂肪量，[Fmin，Fmax]是允许的脂肪范围。每个席也需要约束

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

最小化或最大化，其中Ci为常量。通过更改Ci，可以获得不同的有效解决方案。获得所有有效的解决方案，甚至更弱的解决方案，计算有效解决方案的数量，是一个困难得多的问题。

Answer 2

如果数学规划目前太难，也许可以从随机爬山者开始。

您描述的这个问题让人想起混合问题。这里有一个我发现的迷你锌溶液（一个玩具例子）。