Почему функция min_coins возвращает 0 вместо ожидаемого результата?

Question

Задача: Определите минимальное количество монет, необходимое для размена суммы S. Доступны монеты заданного номинала.

написал код и когда ввожу где coins 100, а где amount [1,5,10,50], то вместо 2 выводит 0, почему?

def min_coins(coins, amount):
    y=0
    z=0
    while coins>=0:
        if len(amount)>0 and coins!=0:
            x=max(amount)
            if coins%x==0:
                z=(coins//x)
                y=y+z
                coins=coins-z*x
                amount.remove(x)
            elif x<coins:
                z=1
                y=y+z
                coins=coins-x
            else:
                amount.remove(x)
        else:
            print('0')
            return
    print(y)

Пробовал и другой код, но понял что он точно неправильный.

Примеры для ввода и вывод:

min_coins(100, [1, 5, 10, 50])---2
min_coins(0, [1, 5, 10])---0
min_coins(99, [1, 3, 7, 12, 25, 50])---4
min_coins(15, [1, 7, 10])---3

Answer 1

Одна ошибка в заголовке цикла while. Условие неверное.

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

Answer 2

import os

def min_coin_usage(v_target_amount, v_coin_denominations):

 # Инициализация массива минимального количества монет для каждой суммы
 # Индекс — сумма, значение — минимальное количество монет для её получения
 v_min_coin_count = [float('inf')] * (v_target_amount + 1)
 v_min_coin_count[0] = 0  # Для суммы 0 нужно 0 монет

 # Инициализация массива для хранения последней использованной монеты
 # Индекс — сумма, значение — номинал монеты, использованной для получения этой суммы
 v_last_coin_used = [-1] * (v_target_amount + 1)

 # Динамический перебор всех возможных сумм от 1 до целевой
 for v_amount in range(1, v_target_amount + 1):
  for v_coin in v_coin_denominations:
   if v_coin <= v_amount:
    v_previous_amount = v_amount - v_coin
    v_candidate_count = v_min_coin_count[v_previous_amount] + 1
    if v_candidate_count < v_min_coin_count[v_amount]:
     v_min_coin_count[v_amount] = v_candidate_count
     v_last_coin_used[v_amount] = v_coin

 # Проверка: если сумма недостижима — выбрасываем исключение
 if v_min_coin_count[v_target_amount] == float('inf'):
  raise ValueError("Сумму невозможно разменять заданными номиналами.")

 # Определение набора монет, использованных для размена
 # Формируем словарь: ключ — номинал, значение — количество использованных монет
 v_coin_usage = {}
 v_remaining_amount = v_target_amount

 while v_remaining_amount > 0:
  v_used_coin = v_last_coin_used[v_remaining_amount]
  if v_used_coin == -1:
   raise RuntimeError("Ошибка определения набора монет.")
  v_coin_usage[v_used_coin] = v_coin_usage.get(v_used_coin, 0) + 1
  v_remaining_amount -= v_used_coin

 # Возвращаем структуру с количеством монет каждого номинала
 return v_coin_usage

# Пример использования:
# v_input_amount = 12
v_input_amount = 100
# v_available_coins = [10, 6]
v_available_coins = [50, 10, 5, 1]

# Получение результата
v_result = min_coin_usage(v_input_amount, v_available_coins)

# Вывод результата
print(f"Сумма: {v_input_amount}")
print(f"Набор монет: {v_available_coins}")
v_sorted_output = sorted(v_result.items(), reverse=True)
v_coin_list = [f"{v_count}×{v_coin}" for v_coin, v_count in v_sorted_output]
print(f"Набор монет: {', '.join(v_coin_list)}")
print(f"Минимальное количество монет: {sum(v_result.values())}")

os.system("pause")

БЛОГ НА HUSL

Почему функция min_coins возвращает 0 вместо ожидаемого результата?

Ответы (2 шт):