Question

В магазине продается печенье в ящиках по 15 кг, 17 кг, 21 кг. Как купить ровно 185 кг печеньи, не вскрывая ящики? Сколькими способами можно это сделать? PYTHON python

Answer 1

def find_combinations(total_weight: int, box_weights: list):

   result = []

   for x in range(total_weight // box_weights[0] + 1):

       for y in range(total_weight // box_weights[1] + 1):

           for z in range(total_weight // box_weights[2] + 1):

               if box_weights[0] * x + box_weights[1] * y + box_weights[2] * z == total_weight:

                   result.append((x, y, z))

   return result

box_weights = [15, 17, 21]

total_weight = 185

combinations = find_combinations(total_weight, box_weights)

print(f'Всего {len(combinations)} способов купить {total_weight} кг печенья:')

for combination in combinations:

   print(f'{box_weights[0]} кг x {combination[0]}, {box_weights[1]} кг x {combination[1]}, {box_weights[2]} кг x {combination[2]}')

Можно сделать по другому и проще используя библиотеку itertools

from itertools import product

box_weights = [15, 17, 21]

total_weight = 185

combinations = [combination for combination in product(range(total_weight // box_weights[0] + 1), range(total_weight // box_weights[1] + 1), range(total_weight // box_weights[2] + 1)) if sum([box_weights[i] * combination[i] for i in range(len(box_weights))]) == total_weight]

print(f'Всего {len(combinations)} способов купить {total_weight} кг печенья:')

for combination in combinations:

   print(f'{box_weights[0]} кг x {combination[0]}, {box_weights[1]} кг x {combination[1]}, {box_weights[2]} кг x {combination[2]}')

Answer 2

Для решения этой задачи можно воспользоваться методом динамического программирования. Мы можем создать массив, в котором будем отслеживать количество способов получить каждый возможный вес печенья от 0 до 185 кг. Начнем с нулевого веса и будем поочередно добавлять каждый из доступных весов печенья (15 кг, 17 кг и 21 кг), обновляя количество способов для каждого веса. Затем, когда мы достигнем 185 кг, мы сможем узнать количество способов, которыми можно получить этот вес.

Вот Python-код для решения задачи:

pythonCopy code
def count_ways_to_reach_target_weight(target_weight):
    # Создаем массив для отслеживания количества способов для каждого веса от 0 до target_weight.
    # Изначально все значения устанавливаются в 0, кроме 0, у нас есть 1 способ достичь веса 0 - не покупать печенье.
    ways = [0] * (target_weight + 1)
    ways[0] = 1

    # Доступные веса печенья.
    cookie_weights = [15, 17, 21]

    # Для каждого веса от 1 до target_weight.
    for weight in range(1, target_weight + 1):
        # Для каждого доступного веса печенья.
        for cookie_weight in cookie_weights:
            # Если текущий вес больше или равен весу печенья, добавляем способы из предыдущего веса.
            if weight >= cookie_weight:
                ways[weight] += ways[weight - cookie_weight]

    return ways[target_weight]

# Заданный вес печенья.
target_weight = 185

# Подсчитываем количество способов.
result = count_ways_to_reach_target_weight(target_weight)
print(f"Количество способов купить {target_weight} кг печенья: {result}")

Этот код создает массив ways, где ways[i] содержит количество способов достичь веса i. Мы заполняем его, перебирая доступные веса печенья и обновляя количество способов для каждого веса от 1 до target_weight. В конечном итоге, значение ways[target_weight] содержит количество способов купить ровно 185 кг печенья без вскрытия ящиков.