我有这个问题:您需要根据用户输入的数据制定膳食计划。我们有一个包含每餐和价格的数据库(每餐也有一个标记，因为我们在早餐上吃的东西通常与午餐和晚餐不同)。输入接收钱数(货币不重要)和天数。在输出中，我们必须得到给定天数的膳食制度。条件:
- 最终价格与给定价格相差不超过3%。
- 每5天用餐不得超过一次。
我发现这不是一个有效的解决方案:我们寻找的是每天的平均价格=金额/天数。然后，直到我们达到给定的天数，我们遍历每个早餐，然后是午餐和晚餐(3个for循环，2个嵌套)，如果价格没有太大差异，那么我们结束搜索并将这一天添加到结果列表中。所以设计现在看起来像这样:
while(daysCounter < days){
for(){
for(){
for(){
}
}
看起来很可怕，虽然没有很多数据(用餐次数约为150次)。有人认为有可能找到一个更有效的解决办法。我也考虑动态规划，但到目前为止还没有想法如何实现它。
动态规划不起作用，因为您的状态的必要部分是过去5天的膳食。而这种可能性的数量是天文数字。
然而，很可能有许多解决方案，而不仅仅是几个。通过贪婪，很容易找到一个有效的解决方案。而且，现有的解决方案可以相当容易地改进。
我可以这样解。用一系列的食物来代替一天。算出你想花的钱。瓜分了它在饮食中,比例的平均价格期权餐。(早餐通常比晚餐便宜。)现在把每顿饭的成本加起来，得到总成本。
现在，为每顿饭选择你最近5天没有吃的饭，使总花费尽可能接近理想总额。选择你所有的饭菜，一次一顿。
这是贪婪的方法。通常情况下，但并非总是如此，它会相当接近目标。
现在,最多n尝试或直到你有目标在3%以内,选择一个随机的餐,考虑所有选项没有吃在过去或未来5天,并随机选择一个(如果存在任何此类选项)带来的整体支出接近目标。
(对于可能在很长一段时间内变化更大的膳食计划，我建议尝试模拟退火。这将产生更有趣的结果，但也将花费更长的时间。