Python возвращает список элементов, которые соответствуют заданным параметрам

ProgramBox

Python возвращает список элементов, которые соответствуют заданным параметрам

Post author:admin
Запись опубликована:11 марта, 2023
Post category:Вопросы по программированию

#python #algorithm #iteration #scientific-computing

#python #алгоритм #итерация #научные вычисления

Вопрос:

У меня возникли некоторые трудности с правильной упаковкой возвращенного решения в 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)

1. используйте генетический алгоритм

2. Вы могли бы использовать генетический алгоритм, но с линейной целью и линейными ограничениями вам, вероятно, лучше использовать смешанное целочисленное программирование: developers.google.com/optimization/mip /…

3. @DavidEisenstat спасибо, что указали мне на Google ИЛИ-Tools. я не знал об этом ресурсе, и я не знал языка, необходимого для поиска чего-то подобного. приветствия 🙂

4. Я не уверен , но разве это не может быть решено с помощью варианта knapsack ? Он вычисляет матрицу C[i,w] с максимально возможным значением, используя первые i элементы, которые весят меньше w . Предположим, что калория является весом, а бюджет — значением. После C вычисления найдите ячейки, в которых min_cal <= w <= max_cal находится наибольшее значение, которое ниже бюджета.

5. мне кажется, что это обычная проблема с рюкзаком, но с 2 ограничениями, и лучшим способом решения является динамическое программирование. Я бы предположил, что это какая-то проблема с экзаменом / собеседованием? смотрите здесь, чтобы узнать больше en.wikipedia.org/wiki/List_of_knapsack_problems или более конкретно здесь en.wikipedia.org/wiki/Packing_problems

Ответ №1:

Вероятно, мы можем придумать что-то рекурсивное.

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

Было бы несколько способов ускорить это. Во-первых, создавая рекурсивный кэш, а во-вторых, используя вместо этого подход динамического программирования (т. Е. Начинайте снизу, а не сверху).

1. это действительно полезно, но я не понимаю, как работает лямбда-функция. Как вычисляется вторая половина выражения и почему выражение заключено в квадратные скобки? Я чувствую, что мне здесь не хватает чего-то фундаментального, и у меня возникают проблемы с поиском того, что выглядит как адекватная аналогия в документах python.

2. @Да. лямбда принимает каждую комбинацию (список dicts) и возвращает то, что по сути является 2-кортежем: z минус сумма 'y' для каждого dict в нем и отрицательная сумма 'x' для каждой суммы в нем. Функции sorted() , min() , и т.д. могут принимать итеративные элементы в качестве ключей, которые сообщают им, как сортировать, и сравнивать элементы в порядке приоритета — элементы за пределами первого используются в качестве тай-брейка, если элементы перед ними являются законными. Я использую квадратные скобки, чтобы сделать его списком вместо кортежа без какой-либо причины, кроме того, чтобы сделать выражение немного более понятным.

3. я обновил проблему, чтобы внести некоторую ясность в проблему, и я был бы очень признателен за ваш вклад.

4. Я получаю KeyError: 'x' строку 3 smallest_combo() для примера из вопроса.

5. @greybeard Имейте в виду, что этот код был создан для соответствия этому конкретному примеру ввода, где у каждого dict есть ключи 'name' , 'x' , и 'y' . Вам необходимо убедиться, что это так и в вашей ситуации, или изменить, на что ссылаются переменные, или добавить обработку ошибок.

Ответ №2:

Вот решение для динамического программирования, которое создает структуру данных, показывающую все (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

1. это интересный подход, но я столкнулся с ошибкой при запуске этого со следующим сценарием: рекомендация = menu_recommendation(меню, 800, 1000, 4) Я ожидал получить пустой список с указанием возможных решений, но вместо этого я получил рекомендацию со следующим: общая стоимость: всего 5калорий: 800 общая стоимость превышает доступный бюджет. Я скорректировал код следующим образом и, похоже, вернулся на правильный путь, получив None: если new_key нет в recommendation_tree и new_key[0] <= max_cal и new_key[1] <= budget:

2. В своем описании вы сказали, что хотите быть как можно ближе к бюджету. Если вы просто хотите не превышать бюджет, я могу сделать поиск самого дешевого решения в правильном диапазоне калорий намного более эффективным.

3. Это не всегда будет дешевле, но это будет в рамках бюджета. И обычно это будет дешево.

4. звучит здорово, я бы хотел увидеть ваше более эффективное решение. Самый дешевый для этого нежелателен. На самом деле наиболее желательное решение ближе всего к бюджету без превышения бюджета, в то время как min_cal <= total_cal <= max_cal . Я обновлю описание, чтобы оно было более понятным 🙂

5. @Да. Эффективно просто выполнить поиск A * для самого дешевого пути к нужному диапазону калорий. Но это не будет работать для ваших критериев так же хорошо, как это.

Ответ №3:

Я придумал это, это в основном рюкзак, но он рекурсивно удаляет блюда из меню, если они не подходят для рекомендации:

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

Он удаляет элементы в соответствии с соотношением калорий / затрат, потому что это стоимость, к которой применяется рюкзак.

Пожалуйста, дайте мне знать, если у вас есть какие-либо вопросы.

Ответ №4:

Я полагаю, что решил проблему с рекомендациями, которые находились за пределами границ 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}')

Если у кого-то есть какие-либо улучшения, я хотел бы их услышать!