Minimum Cards
National Olympiad — Municipal round (2023 season)
Submission name: sum.cpp
Problem summary
There are unlimited cards of N distinct positive denominations, including 1. Find the fewest cards whose values sum to S.
Input
S and N, then the N denominations.
Output
The minimum number of cards needed.
Constraints
0 < S < 20000; 0 < N < 2000; all denominations are distinct and between 1 and S; one is 1.
Worked example
An independently prepared example for this explanation.
Input
22 5 1 4 8 12 15
Output
4
Solution analysis
- Let best[s] be the minimum cards needed to form sum s. Initialize best[0]=0. For positive sums, try every denomination v that does not exceed s, using best[s−v]+1.
- Compute sums in increasing order. Since every denomination is positive, best[s−v] is already known. Unlimited supply means the same denomination may appear in that smaller solution again.
- For S=22 and denominations 1,4,8,12,15, the recurrence finds 22=12+8+1+1 with four cards. Greedily taking 15 first would need at least five cards, which shows why choosing the largest available card is insufficient.
Why it works
Any nonempty optimal collection for sum s has some last card v. Removing it leaves a solution for s−v and therefore uses at least best[s−v] cards. Conversely, appending v to an optimal smaller solution realizes each recurrence candidate. Induction on s proves the computed minimum.
Watch out. Cards can be reused, so this is not a 0/1 selection. The presence of denomination 1 guarantees every required sum is reachable.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
// Algorithm: Let best[s] be the minimum cards needed to form sum s.
using namespace std;
int main(){
int target,n;
cin>>target>>n;
vector<int>denomination(n);
for(int&value:denomination){
cin>>value;
}
vector<int>best(target+1,target+1);
best[0]=0;
for(int sum=1;sum<=target;++sum){
for(int value:denomination){
if(value<=sum){
best[sum]=min(best[sum],best[sum-value]+1);
}
}
}
cout<<best[target]<<'\n';
}