零錢問題多種不同的題型

湊零錢問題

1. 給定不同面值的硬幣和一個金額，求最少需要多少個硬幣來湊成這個金額。這涉及到動態規劃等技巧。

   # 湊零錢問題-最少硬幣數目 (找零錢、最少需要幾個錢幣)
   n, total = 3, 11
   coins = [1, 2, 5]
   
   dp = [float('inf')] * (total + 1)
   dp[0] = 0  # 湊成金額為0時，所需硬幣數量為0
   
   for coin in coins:
       for i in range(coin, total + 1):
           dp[i] = min(dp[i], dp[i - coin] + 1)
   
   print(dp[total])

找零錢方法數問題

2. 給定不同面值的硬幣和一個金額，求有多少種不同的方法可以用這些硬幣湊成該金額。

   # 找零錢方法數問題-不同方法數 硬幣 (有幾種方法)
   n, total = 3, 10
   coins = [2, 3, 10]
   
   dp = [0] * (total + 1)
   dp[0] = 1  # 不使用任何硬幣也是一種方式
   
   for coin in coins:
       for i in range(coin, total + 1):
           dp[i] += dp[i - coin]
           # print(f"{dp[i]} += {dp[i-coin]}, {i} {i-coin}")
   # print(dp)
   print(dp[total])

列舉所有找零方法

3. 給定不同面值的硬幣和一個金額，列舉出所有可能的找零方法。

   # 1102 P 錢幣
   
   # 如果之前已經可以組合出總和值 i 或者使用數字 coin 可以組合出總和值 i - coin，
   # 則表示使用數字 coin 也可以組合出總和值 i，將 dp[i] 設置為 1
   
   n = int(input())
   coins = list(map(int, input().split()))
   max_total = sum(coins)
   
   dp = [0] * (max_total + 1)
   dp[0] = 1
   
   for coin in coins:
       for i in range(max_total, coin - 1, -1):
           dp[i] = dp[i] or dp[i - coin]
   
   ans = [i for i in range(1, len(dp)) if dp[i]]
   
   print(len(ans))
   print(*ans, sep=' ')

特定找零方法

4. 給定不同面值的硬幣和一個金額，問是否存在特定的找零方法，或者求一個具體的找零方法。

Contributors

lucashsu95

Changelog

Last edited over 1 year ago

View full history

707c447-init