我在將返回的解決方案正確裝箱為 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)
4 回答
慕工程0101907
TA貢獻1887條經驗 獲得超5個贊
我想出了這個，它基本上是一個背包，但如果不適合推薦，它會從菜單中遞歸刪除菜肴：
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 get_price(recommendation):
return sum(dish["cost"] for dish in recommendation)
def get_calories(recommendation):
return sum(dish["calories"] for dish in recommendation)
def menu_recommendation(menu, min_cal, max_cal, budget):
sorted_menu = sorted(menu, key=lambda dish: dish["cost"], reverse=True)
recommendation = []
for dish in sorted_menu:
if dish["cost"] + get_price(recommendation) <= budget:
recommendation.append(dish)
if recommendation:
if get_calories(recommendation) < min_cal:
sorted_menu.remove(min(recommendation, key=lambda dish: dish["calories"]/dish["cost"]))
return menu_recommendation(sorted_menu, min_cal, max_cal, budget)
if get_calories(recommendation) > max_cal:
sorted_menu.remove(max(recommendation, key=lambda dish: dish["calories"]/dish["cost"]))
return menu_recommendation(sorted_menu, min_cal, max_cal, budget)
return recommendation
recommendation = 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}')
它根據卡路里/成本率刪除元素，因為這是應用背包的成本。
如果您有任何疑問，請告訴我。
ibeautiful
TA貢獻1993條經驗 獲得超6個贊
(calorie, cost)這是一個動態編程解決方案，它構建了一個數據結構，顯示我們可以最終得到的所有選項以及每個選項。我們尋找符合標準的最佳方案，然后找到推薦方案。
def menu_recommendation(menu, min_cal, max_cal, budget):
# This finds the best possible solution in pseudo-polynomial time.
recommendation_tree = {(0, 0.0): None}
for item in menu:
# This tree will wind up being the old plus new entries from adding this item.
new_recommendation_tree = {}
for key in recommendation_tree.keys():
calories, cost = key
new_recommendation_tree[key] = recommendation_tree[key]
new_key = (calories + item['calories'], cost + item['cost'])
if new_key not in recommendation_tree and new_key[0] <= max_cal:
# This is a new calorie/cost combination to look at.
new_recommendation_tree[new_key] = item
# And now save the work.
recommendation_tree = new_recommendation_tree
# Now we look for the best combination.
best = None
for key in recommendation_tree:
calories, cost = key
# By construction, we know that calories <= max_cal
if min_cal <= calories:
if best is None or abs(budget - cost) < abs(budget - best[1]):
# We improved!
best = key
if best is None:
return None
else:
# We need to follow the tree back to the root to find the recommendation
calories, cost = best
item = recommendation_tree[best]
answer = []
while item is not None:
# This item is part of the menu.
answer.append(item)
# And now find where we were before adding this item.
calories = calories - item['calories']
cost = cost - item['cost']
best = (calories, cost)
item = recommendation_tree[best]
return answer
GCT1015
TA貢獻1827條經驗 獲得超4個贊
也許我們可以做一些遞歸的事情。
def smallest_combo(lst, m, n, z):
# filter list to remove elements we can't use next without breaking the rules
lst = [dct for dct in lst if m <= dct['x'] <= n and dct['y'] <= z]
# recursive base case
if len(lst) == 0:
return []
# go through our list of eligibles
# simulate 'what would the best possibility be if we picked that one to go with next'
# then of those results select the one with the sum('y') closest to z
# (breaking ties with the largest sum('x'))
return min((
[dct] + smallest_combo(lst, m - dct['x'], n - dct['x'], z - dct['y'])
for dct in lst
), key=
lambda com: [z - sum(d['y'] for d in com), -sum(d['x'] for d in com)]
)
inp = [{'name': 'item1', 'x': 600, 'y': 5},
{'name': 'item2', 'x': 200, 'y': 8},
{'name': 'item3', 'x': 500, 'y': 12.5},
{'name': 'item4', 'x': 0, 'y': 1.5},
{'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}]
有多種方法可以加快這一速度。首先通過制作遞歸緩存，然后采用動態編程方法（即從底部開始而不是從頂部開始）。
烙印99
TA貢獻1829條經驗 獲得超13個贊
我相信我已經解決了提出超出范圍 min_cal / max_cal 邊界的建議的問題，但我仍然覺得可能有一個更接近預算的解決方案。
這是我更新的代碼：
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) >= 0
and max_cal - sum(item['calories'] for item in recommendations) >= 0,
-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}')
如果有人有任何改進，我很樂意聽到他們的聲音！
添加回答
舉報
0/150
提交
取消