Minimizing Coins

Minimizing Coins
CSES medium

There are \(n\) coins with distinct positive values. You can use each coin any number of times. Find the minimum number of coins with sum exactly \(x\).

Constraints:

  • \(1 \le n \le 100\)
  • \(1 \le x \le 10^6\)
  • \(1 \le c_i \le 10^6\)

Input:

  • First line: two integers \(n\) and \(x\).
  • Second line: \(n\) distinct integers \(c_1, c_2, \dots, c_n\) — the values of the coins.

Output:

  • One integer — the minimum number of coins, or \(-1\) if the sum \(x\) cannot be made.

Example:

Input:

3 11
1 5 7

Output:

3

(\(11 = 5 + 5 + 1\).)

Solution

We use dynamic programming with the state

\(dp_s\) = the minimum number of coins with sum \(s\).

Consider the last coin in an optimal set of coins with sum \(s\). If its value is \(c_i\), the other coins have sum \(s - c_i\), and they must also use as few coins as possible. So

\(dp_s = \min\limits_{c_i \le s} \left( dp_{s - c_i} + 1 \right)\)

with the base case \(dp_0 = 0\). If no coin gives a possible sum \(s - c_i\), the sum \(s\) cannot be made. We mark this with a very large value IMPOSSIBLE, and at the end we print \(-1\) if \(dp_x\) is still IMPOSSIBLE.

We compute \(dp_s\) for \(s = 1, 2, \dots, x\) in this order, because each value uses only smaller sums.

There are \(x\) states and \(n\) transitions for each, so the time complexity is \(O(n \cdot x)\), which is at most \(10^8\) simple operations.

#include <iostream>
#include <algorithm>
using namespace std;

const int IMPOSSIBLE = 1000000000;

int c[100];
int dp[1000001];  // dp[s] = minimum number of coins with sum s

int main() {
    int n, x;
    cin >> n >> x;

    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }

    dp[0] = 0;
    for (int s = 1; s <= x; s++) {
        dp[s] = IMPOSSIBLE;
        // the last coin can be any coin that is not larger than s
        for (int i = 0; i < n; i++) {
            if (c[i] <= s) {
                dp[s] = min(dp[s], dp[s - c[i]] + 1);
            }
        }
    }

    if (dp[x] == IMPOSSIBLE) {
        cout << -1 << "\n";
    } else {
        cout << dp[x] << "\n";
    }
}
NoteCompare with Coin Combinations I

Coin Combinations I uses the same states and transitions, but it adds the values of the transitions to count the ways. Here we take their minimum.