To solve this problem, we need to find the minimum number of coins required to make a given target amount using a set of coin denominations. This is a classic problem that can be efficiently solved using Dijkstra's Algorithm (or BFS, since each coin adds exactly one to the count of coins used). Here, we use Dijkstra's Algorithm to prioritize states with fewer coins, ensuring we find the minimal solution first.

Approach

1. Problem Analysis: We need to reach the target sum using the least number of coins. Each coin can be used multiple times (unbounded knapsack variant).
2. Intuition: Use a priority queue (min-heap) to always expand the state with the fewest coins first. This ensures that the first time we reach the target sum, it's with the minimal number of coins.
3. Optimization: Track the minimal number of coins needed to reach each sum using a visited array. This avoids reprocessing states with higher or equal coin counts.

Solution Code

import heapq

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr +=1
    coins = list(map(int, input[ptr:ptr+N]))
    ptr +=N
    T = int(input[ptr])

    INF = float('inf')
    visited = [INF]*(T+1)
    heap = []
    heapq.heappush(heap, (0,0))  # (number of coins, current sum)
    visited[0] = 0

    while heap:
        count, current = heapq.heappop(heap)
        if current == T:
            print(count)
            return
        for coin in coins:
            next_sum = current + coin
            if next_sum > T:
                continue
            if visited[next_sum] > count + 1:
                visited[next_sum] = count + 1
                heapq.heappush(heap, (count+1, next_sum))
    print(-1)  # If target can't be reached

if __name__ == "__main__":
    main()

Explanation

1. Initialization:
   • visited array: Stores the minimal coins needed to reach each sum (initialized to infinity, except sum 0 which uses 0 coins).
   • Priority queue: Starts with the state (0 coins, sum=0).
2. Processing:
   • Pop the state with the fewest coins from the heap.
   • If the current sum equals the target, return the count of coins (since it's the minimal).
   • For each coin, compute the new sum. If the new sum is within the target and the new coin count is better (fewer) than the existing value in visited, update visited and push the new state to the heap.
3. Result: If the heap is exhausted without reaching the target, return -1 (target can't be formed with given coins).

This approach efficiently finds the minimal coins using Dijkstra's Algorithm, ensuring optimal performance even for larger target values. The time complexity is O(T * log T) (due to heap operations), which is feasible for most practical cases. For even better performance (O(T)), BFS can be used since each step adds exactly one coin (level order traversal gives minimal coins first). However, the given solution is correct and works well for the problem.

作者声明:本文包含人工智能生成内容。