Python 返回符合设置参数的项目列表

Question

我在将返回的解决方案正确装箱为 min_cals <= sum(calories) <= max_cals 时遇到一些困难。有一些组合可以产生 sum(cals) < min_cals 的解决方案。除了保持在热量范围内之外，解决方案还应该生成一个列表，其中总成本尽可能接近预算而不超过预算限制。这是一些重新上下文化的代码。我真的可以帮忙：

menu = [

    {'name':'Cheese Pizza Slice', 'calories': 700, 'cost': 4},

    {'name':'House Salad', 'calories': 100, 'cost': 8.5},

    {'name':'Grilled Shrimp', 'calories': 400, 'cost': 15},

    {'name':'Beef Brisket', 'calories': 400, 'cost': 12},

    {'name':'Soda', 'calories': 100, 'cost': 1},

    {'name':'Cake', 'calories': 300, 'cost': 3},

]

def menu_recommendation(menu, min_cal, max_cal, budget):

    menu = [item for item in menu if item['calories'] <= max_cal and item['cost'] <= budget]

    if len(menu) == 0: return []

    return min((

        [item] + menu_recommendation(menu, min_cal - item['calories'], max_cal - item['calories'], budget - item['cost'])

        for item in menu

    ), key= 

        lambda recommendations: [budget - sum(item['cost'] for item in recommendations) and min_cal <= sum(item['calories'] for item in recommendations) <= max_cal, -sum(item['calories'] for item in recommendations)]

    )

recommendation = menu_recommendation(menu, 1000, 1200, 15)

total_cost = sum(item['cost'] for item in recommendation)

total_cals = sum(item['calories'] for item in recommendation)

print(f'recommendation: {recommendation}')

print(f'total cost: {total_cost}')

print(f'total calories: {total_cals}')

例如，以下命令返回总卡路里数为 700 的解决方案，低于最小值 1000。推荐 = menu_recommendation(菜单, 1000, 1200, 15)

Answer 1

我想出了这个，它基本上是一个背包，但如果不适合推荐，它会从菜单中递归删除菜肴：menu = [&nbsp; &nbsp; {'name':'Cheese Pizza Slice', 'calories': 700, 'cost': 4},&nbsp; &nbsp; {'name':'House Salad', 'calories': 100, 'cost': 8.5},&nbsp; &nbsp; {'name':'Grilled Shrimp', 'calories': 400, 'cost': 15},&nbsp; &nbsp; {'name':'Beef Brisket', 'calories': 400, 'cost': 12},&nbsp; &nbsp; {'name':'Soda', 'calories': 100, 'cost': 1},&nbsp; &nbsp; {'name':'Cake', 'calories': 300, 'cost': 3},]def get_price(recommendation):&nbsp; &nbsp; return sum(dish["cost"] for dish in recommendation)def get_calories(recommendation):&nbsp; &nbsp; return sum(dish["calories"] for dish in recommendation)def menu_recommendation(menu, min_cal, max_cal, budget):&nbsp; &nbsp; sorted_menu = sorted(menu, key=lambda dish: dish["cost"], reverse=True)&nbsp; &nbsp; recommendation = []&nbsp; &nbsp; for dish in sorted_menu:&nbsp; &nbsp; &nbsp; if dish["cost"] + get_price(recommendation) <= budget:&nbsp; &nbsp; &nbsp; &nbsp; recommendation.append(dish)&nbsp; &nbsp; if recommendation:&nbsp; &nbsp; &nbsp; if get_calories(recommendation) < min_cal:&nbsp; &nbsp; &nbsp; &nbsp; sorted_menu.remove(min(recommendation, key=lambda dish: dish["calories"]/dish["cost"]))&nbsp; &nbsp; &nbsp; &nbsp; return menu_recommendation(sorted_menu, min_cal, max_cal, budget)&nbsp; &nbsp; &nbsp; if get_calories(recommendation) > max_cal:&nbsp; &nbsp; &nbsp; &nbsp; sorted_menu.remove(max(recommendation, key=lambda dish: dish["calories"]/dish["cost"]))&nbsp; &nbsp; &nbsp; &nbsp; return menu_recommendation(sorted_menu, min_cal, max_cal, budget)&nbsp; &nbsp; return recommendationrecommendation = menu_recommendation(menu, 500, 800, 15)total_cost = sum(item['cost'] for item in recommendation)total_cals = sum(item['calories'] for item in recommendation)print(f'recommendation: {recommendation}')print(f'total cost: {total_cost}')&nbsp;它根据卡路里/成本率删除元素，因为这是应用背包的成本。如果您有任何疑问，请告诉我。

Answer 2

(calorie, cost)这是一个动态编程解决方案，它构建了一个数据结构，显示我们可以最终得到的所有选项以及每个选项。我们寻找符合标准的最佳方案，然后找到推荐方案。def menu_recommendation(menu, min_cal, max_cal, budget):&nbsp; &nbsp; # This finds the best possible solution in pseudo-polynomial time.&nbsp; &nbsp; recommendation_tree = {(0, 0.0): None}&nbsp; &nbsp; for item in menu:&nbsp; &nbsp; &nbsp; &nbsp; # This tree will wind up being the old plus new entries from adding this item.&nbsp; &nbsp; &nbsp; &nbsp; new_recommendation_tree = {}&nbsp; &nbsp; &nbsp; &nbsp; for key in recommendation_tree.keys():&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; calories, cost = key&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new_recommendation_tree[key] = recommendation_tree[key]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new_key = (calories + item['calories'], cost + item['cost'])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if new_key not in recommendation_tree and new_key[0] <= max_cal:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # This is a new calorie/cost combination to look at.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new_recommendation_tree[new_key] = item&nbsp; &nbsp; &nbsp; &nbsp; # And now save the work.&nbsp; &nbsp; &nbsp; &nbsp; recommendation_tree = new_recommendation_tree&nbsp; &nbsp; # Now we look for the best combination.&nbsp; &nbsp; best = None&nbsp; &nbsp; for key in recommendation_tree:&nbsp; &nbsp; &nbsp; &nbsp; calories, cost = key&nbsp; &nbsp; &nbsp; &nbsp; # By construction, we know that calories <= max_cal&nbsp; &nbsp; &nbsp; &nbsp; if min_cal <= calories:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if best is None or abs(budget - cost) < abs(budget - best[1]):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # We improved!&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; best = key&nbsp; &nbsp; if best is None:&nbsp; &nbsp; &nbsp; &nbsp; return None&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; # We need to follow the tree back to the root to find the recommendation&nbsp; &nbsp; &nbsp; &nbsp; calories, cost = best&nbsp; &nbsp; &nbsp; &nbsp; item = recommendation_tree[best]&nbsp; &nbsp; &nbsp; &nbsp; answer = []&nbsp; &nbsp; &nbsp; &nbsp; while item is not None:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # This item is part of the menu.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; answer.append(item)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # And now find where we were before adding this item.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; calories = calories - item['calories']&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cost = cost - item['cost']&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; best = (calories, cost)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; item = recommendation_tree[best]&nbsp; &nbsp; &nbsp; &nbsp; return answer

Answer 3

也许我们可以做一些递归的事情。def smallest_combo(lst, m, n, z):&nbsp; &nbsp; # filter list to remove elements we can't use next without breaking the rules&nbsp; &nbsp; lst = [dct for dct in lst if m <= dct['x'] <= n and dct['y'] <= z]&nbsp; &nbsp; # recursive base case&nbsp; &nbsp; if len(lst) == 0:&nbsp; &nbsp; &nbsp; &nbsp; return []&nbsp; &nbsp; # go through our list of eligibles&nbsp; &nbsp; # simulate 'what would the best possibility be if we picked that one to go with next'&nbsp; &nbsp; # then of those results select the one with the sum('y') closest to z&nbsp; &nbsp; #&nbsp; &nbsp;(breaking ties with the largest sum('x'))&nbsp; &nbsp; return min((&nbsp; &nbsp; &nbsp; &nbsp; [dct] + smallest_combo(lst, m - dct['x'], n - dct['x'], z - dct['y'])&nbsp; &nbsp; &nbsp; &nbsp; for dct in lst&nbsp; &nbsp; ), key=&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; lambda com: [z - sum(d['y'] for d in com), -sum(d['x'] for d in com)]&nbsp; &nbsp; )inp = [{'name': 'item1', 'x': 600, 'y': 5},&nbsp;{'name': 'item2', 'x': 200, 'y': 8},&nbsp;{'name': 'item3', 'x': 500, 'y': 12.5},&nbsp;{'name': 'item4', 'x': 0, 'y': 1.5},&nbsp;{'name': 'item5', 'x': 100, 'y': 1}]print(smallest_combo(inp, 500, 1500, 25))# [{'name': 'item3', 'x': 500, 'y': 12.5}, {'name': 'item3', 'x': 500, 'y': 12.5}]有多种方法可以加快这一速度。首先通过制作递归缓存，然后采用动态编程方法（即从底部开始而不是从顶部开始）。

Answer 4

我相信我已经解决了提出超出范围 min_cal / max_cal 边界的建议的问题，但我仍然觉得可能有一个更接近预算的解决方案。这是我更新的代码：menu = [&nbsp; &nbsp; {'name':'Cheese Pizza Slice', 'calories': 700, 'cost': 4},&nbsp; &nbsp; {'name':'House Salad', 'calories': 100, 'cost': 8.5},&nbsp; &nbsp; {'name':'Grilled Shrimp', 'calories': 400, 'cost': 15},&nbsp; &nbsp; {'name':'Beef Brisket', 'calories': 400, 'cost': 12},&nbsp; &nbsp; {'name':'Soda', 'calories': 100, 'cost': 1},&nbsp; &nbsp; {'name':'Cake', 'calories': 300, 'cost': 3},]def menu_recommendation(menu, min_cal, max_cal, budget):&nbsp; &nbsp; menu = [item for item in menu if item['calories'] <= max_cal and item['cost'] <= budget]&nbsp; &nbsp; if len(menu) == 0: return []&nbsp; &nbsp; return min(([item] + menu_recommendation(menu, min_cal - item['calories'], max_cal - item['calories'], budget - item['cost'])&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; for item in menu), key=&nbsp;&nbsp; &nbsp; lambda recommendations: [budget - sum(item['cost'] for item in recommendations)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;and min_cal - sum(item['calories'] for item in recommendations) >= 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;and max_cal - sum(item['calories'] for item in recommendations) >= 0,&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-sum(item['calories'] for item in recommendations)])recommendation = menu_recommendation(menu, 1000, 1200, 15)total_cost = sum(item['cost'] for item in recommendation)total_cals = sum(item['calories'] for item in recommendation)print(f'recommendation: {recommendation}')print(f'total cost: {total_cost}')print(f'total calories: {total_cals}')如果有人有任何改进，我很乐意听到他们的声音！