Coin Change — Minimum Coins

Minimum coin change finds a shortest exact-sum representation with unlimited copies of positive denominations. It resembles unbounded knapsack, but stores a minimum number of actions and must distinguish unreachable amounts. A final-coin recurrence is exact for arbitrary denominations, unlike largest-coin greedy. The program also reconstructs one optimal multiset of coins.

Prerequisites: Unbounded Knapsack; unreachable sentinels; reconstruction. Related existing lessons: Coin Change — Greedy Approach.

Build the idea

1. Recognize the repeated subproblems

   Every ordered choice history reaching amount x has the same remaining denominations available. Enumerating sequences repeats these amounts; one state per x suffices. A moderate target up to 200000 allows n·target transitions. Positive denominations are crucial: they make each dependency a smaller amount and exclude zero-length transitions.

2. Define the state

   dp[x] is the minimum number of coins totaling exactly x; A+1 represents unreachable because any reachable amount≤A uses at most A positive integer coins. choice[x] stores the last coin of an improving transition. Unlike at-most-capacity knapsack, choosing nothing is not a feasible answer for every positive x.

3. Derive the transition

   If the last coin is c≤x, removing it leaves x−c, so compare dp[x−c]+1 over denominations. The code sorts coins for deterministic tie behavior and updates only on strict improvement. An unreachable predecessor has dp=A+1 and adding one does not improve a state; the bounded sentinel makes this arithmetic safe. Every candidate constructs a legal exact sum.

   $$\mathrm{dp}\left[x\right]=\min \left\{\mathrm{dp}\right[x-c]+1:c\le x\}$$

4. Base cases and computation order

   Set dp[0]=0 and fill x=1…A. No recursive stack is needed because x−c<x. If dp[A] stays sentinel, print −1. Otherwise repeatedly subtract choice[x] to recover the coins. Each subtraction is positive and decreases x, so reconstruction terminates at zero. At A=0 the empty representation has zero coins.

5. Correctness and invariant

   Induct on amount. Every feasible representation has a final coin and therefore cannot beat the best predecessor candidate; appending a chosen coin attains the recurrence. Overlapping histories are safely merged because they have identical future options. Order among reconstructed coins is irrelevant to minimum count; changing the objective to counting representations requires careful loop semantics.

6. Work the example

   Coins {1,3,4}, target 6 produce dp values 0,1,2,1,1,2,2. State 6 improves from three coins via 1 to two via 3, giving 3+3. Largest-first greedy instead commits to 4 and needs two ones, so its count is three. The program’s witness and value make that difference concrete.

   amount	0	1	2	3	4	5	6
   minimum coins	0	1	2	1	1	2	2

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
int main(){
    int n,A;
    std::cin>>n>>A;
    std::vector<int>coins(n);
    for(int&c:coins){
        std::cin>>c;
    }
    std::sort(coins.begin(),coins.end());
    std::vector<int>dp(A+1,A+1),choice(A+1);
    dp[0]=0;
    for(int x=1;x<=A;++x){
        for(int c:coins){
            if(c<=x&&dp[x-c]+1<dp[x]){
                dp[x]=dp[x-c]+1;
                choice[x]=c;
            } // Positive coins make every dependency smaller.
        }
    }
    if(dp[A]==A+1){
        std::cout<<-1<<'\n';
        return 0;
    }
    std::cout<<dp[A]<<'\n';
    std::vector<int>used;
    for(int x=A;x>0;x-=choice[x]){
        used.push_back(choice[x]);
    }
    for(int i=0;i<(int)used.size();++i){
        std::cout<<used[i]<<(i+1==(int)used.size()?'\n':' ');
    }
    if(used.empty()){
        std::cout<<'\n';
    }
}

Complexity analysis

A+1 states, up to n predecessor coins each: O(nA+n log n) time including sorting; O(A+n) arrays/input plus O(A) worst-case witness output. Counts are at most A, so int suffices here.

Example input and output

Read n A (1≤n≤100,0≤A≤200000), then n positive denominations≤10^6, unlimited copies. Print −1 if impossible; otherwise minimum count and an optimal list of coin values.

Input

3 6
1 3 4

Output

2
3 3

Coins {1,3,4}, target 6 produce dp values 0,1,2,1,1,2,2. State 6 improves from three coins via 1 to two via 3, giving 3+3. Largest-first greedy instead commits to 4 and needs two ones, so its count is three. The program’s witness and value make that difference concrete.

Practical applications

Use for minimum repeated actions with additive integer progress. For huge arbitrary amounts this table may be too large; number-theory or residue-graph methods can help in specific models. The Greedy folder supplies a direct greedy/DP comparison.

Check your understanding

What value should dp[0] have?

Put it into practice

Try coins {3,4} with target 6 and target 5.