Python return list of items that fit set parameters

We can work up something recursive, probably.

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}]

There would be a number of ways to speed this up. First by making a recursive cache, and second by taking a dynamic programming approach instead (i.e. start at the bottom instead of at the top).

Here is a dynamic programming solution that builds up a data structure showing all of the (calorie, cost) options we can wind up with along with one item each. We look for the best one meeting the criteria, then find what recommendation that is.

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

I came up with this, it's basically a knapsack but it removes recursively dishes from the menu if they are not suitable for the recommendation:

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}')
 

It removes elements according to the calorie/cost rate, because it's the cost to which is applied the knapsack.

Please let me know if you have any question.

I believe I have solved the issue of making recommendations that were outside of the scoped min_cal / max_cal boundaries, but I still feel like there could be a solution that more closely approaches budget.

Here is my updated code:

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}')

If anyone has any improvements I'd love to hear them!