Proof Needed: Minimum # of coins needed to make a given sum

Question

We have infinite supply of these 5 coins: $1, 3, 6, 10, 15$

Find the minimum number of these coins required such that their total value sums up to exactly $n$.

Example:
For $n = 425$, answer is $29$.
Explanation:
$27 \times 15 = 405$ and $2 \times 10 = 20$.
$27$ coins of 15-value and $2$ coins of 10-value give the optimal answer.

My Approach:

• Realise that when n grows, say n = 420, its 15 x 28 and 10 x 42, and 42-28 = 14
• This means using the 15-value coin is a no-brainer as its using atleast 14 less coins than other combinations, so even if the remainder is non-zero, it will be less than or equal to 14 and we can use 1-value coin to fill the remainder, and it will still be optimal.
• So I reduce large values of n, say 10^9 to a number between 420 and 435 by using only 15-value coins, then I rely on dynamic programming to tell me the minimal coins needed to consume the current number.

This works right, but I am not able to prove this how the corner case of using two 10-coins optimally was also covered by this approach. I kind of believe given we covered all cases from 420 to 435 using dynamic programming, any number beyond 435 gets reduced to 420 to 435 range and that range covers all corner cases of using other smaller coins optimally. A formal proof will help.

My below solution got accepted and passed all test cases: https://codeforces.com/contest/1934/submission/249410271

#include <bits/stdc++.h>
using namespace std;
int dp[435];
int go(int n) {
    if (n >= 435) return (n-420)/15 + go(420 + (n-420)%15);
    return dp[n];
}
void solve() {
    int n; cin >> n;
    cout << go(n) << endl;
}
void init() {
    vector<int> coins = {1, 3, 6, 10, 15};
    dp[0] = 0;
    for (int i = 1; i < 435; i++) {
        dp[i] = i;
        for (int c: coins) if (c <= i) dp[i] = min(dp[i], 1 + dp[i-c]);
    }
}
int main() {
    init();
    solve();
    return 0;
}

Answer 1

Consider you have an optimal configuration that sums to $n$. Then you must have:

• $\le 2$ coins of value 1
• $\le 1$ coins of value 3
• $\le 2$ coins of value 6
• $\le 2$ coins of value 10

Otherwise, we may replace smaller coins with larger coins.

So, if you remove the coins of value 15, the other coins sum to at most 37.

You can manually search for the optimum configuration for $1\le n\le37$. Other values of $n$ can be reduced to this by coins of value 15.

---

Your approach might work, but I don't think it is logically sound.
You say that "Realise that when n grows, say n = 420, its 15 x 28 and 10 x 42, and 42-28 = 14". This is not right. To get an optimum configuration, we don't have to swap all the 28 15 value coins with 42 10 value coins, even a 2:3 ratio might work.