Problem
Given a list of 'N' coins, their values being in an array A[], return the minimum number of coins required to sum to 'S' (you can use as many coins you want). If it's not possible to sum to 'S', return -1
Input #01:
Coin denominations: { 5,5,5,5,5 }
Required sum (S): 11
Output #01:
-1
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Number maze
Created Date : 20-September-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <vector>
#include <limits>
using namespace std;
int FindChangeNum(vector<int> coins, int s)
{
vector<int> nums(s + 1, -1);
nums[0] = 0;
for(int i = 0; i < nums.size(); ++i){
for(int j: coins){
if(i + j <= s){
if(nums[i] != -1 &&
nums[i + j] != -1){
nums[i + j] = min(nums[i] + 1, nums[i + j]);
}
else if(nums[i] != -1 &&
nums[i + j] == -1){
nums[i + j] = nums[i] + 1;
}
}
}
}
return nums[s];
}
void DoTest(vector<int> coins, int s)
{
cout << "Coin denominations: " << endl;
for(auto i: coins){
cout << setw(4) << " " << i;
}
cout << endl;
cout << "Required sum(s) :" << s << endl;
cout << "Output: " << FindChangeNum(coins, s) << endl;
cout << "---------------------------\n" << endl;
}
int main(int argc, char* argv[])
{
int coins0[] = {5, 2};
vector<int> coins( coins0, coins0 + sizeof(coins0) / sizeof(int));
for(int i = 0; i < 20; i ++){
DoTest(coins, i);
}
int coins1[] = {5, 7, 2};
coins.assign(coins1, coins1 + sizeof(coins1) / sizeof(int));
for(int i = 0; i < 20; i ++){
DoTest(coins, i);
}
return 0;
}
Output
Coin denominations:
5 2
Required sum(s) :0
Output: 0
---------------------------
Coin denominations:
5 2
Required sum(s) :1
Output: -1
---------------------------
Coin denominations:
5 2
Required sum(s) :2
Output: 1
---------------------------
Coin denominations:
5 2
Required sum(s) :3
Output: -1
---------------------------
Coin denominations:
5 2
Required sum(s) :4
Output: 2
---------------------------
Coin denominations:
5 2
Required sum(s) :5
Output: 1
---------------------------
Coin denominations:
5 2
Required sum(s) :6
Output: 3
---------------------------
Coin denominations:
5 2
Required sum(s) :7
Output: 2
---------------------------
Coin denominations:
5 2
Required sum(s) :8
Output: 4
---------------------------
Coin denominations:
5 2
Required sum(s) :9
Output: 3
---------------------------
Coin denominations:
5 2
Required sum(s) :10
Output: 2
---------------------------
Coin denominations:
5 2
Required sum(s) :11
Output: 4
---------------------------
Coin denominations:
5 2
Required sum(s) :12
Output: 3
---------------------------
Coin denominations:
5 2
Required sum(s) :13
Output: 5
---------------------------
Coin denominations:
5 2
Required sum(s) :14
Output: 4
---------------------------
Coin denominations:
5 2
Required sum(s) :15
Output: 3
---------------------------
Coin denominations:
5 2
Required sum(s) :16
Output: 5
---------------------------
Coin denominations:
5 2
Required sum(s) :17
Output: 4
---------------------------
Coin denominations:
5 2
Required sum(s) :18
Output: 6
---------------------------
Coin denominations:
5 2
Required sum(s) :19
Output: 5
---------------------------
Coin denominations:
5 7 2
Required sum(s) :0
Output: 0
---------------------------
Coin denominations:
5 7 2
Required sum(s) :1
Output: -1
---------------------------
Coin denominations:
5 7 2
Required sum(s) :2
Output: 1
---------------------------
Coin denominations:
5 7 2
Required sum(s) :3
Output: -1
---------------------------
Coin denominations:
5 7 2
Required sum(s) :4
Output: 2
---------------------------
Coin denominations:
5 7 2
Required sum(s) :5
Output: 1
---------------------------
Coin denominations:
5 7 2
Required sum(s) :6
Output: 3
---------------------------
Coin denominations:
5 7 2
Required sum(s) :7
Output: 1
---------------------------
Coin denominations:
5 7 2
Required sum(s) :8
Output: 4
---------------------------
Coin denominations:
5 7 2
Required sum(s) :9
Output: 2
---------------------------
Coin denominations:
5 7 2
Required sum(s) :10
Output: 2
---------------------------
Coin denominations:
5 7 2
Required sum(s) :11
Output: 3
---------------------------
Coin denominations:
5 7 2
Required sum(s) :12
Output: 2
---------------------------
Coin denominations:
5 7 2
Required sum(s) :13
Output: 4
---------------------------
Coin denominations:
5 7 2
Required sum(s) :14
Output: 2
---------------------------
Coin denominations:
5 7 2
Required sum(s) :15
Output: 3
---------------------------
Coin denominations:
5 7 2
Required sum(s) :16
Output: 3
---------------------------
Coin denominations:
5 7 2
Required sum(s) :17
Output: 3
---------------------------
Coin denominations:
5 7 2
Required sum(s) :18
Output: 4
---------------------------
Coin denominations:
5 7 2
Required sum(s) :19
Output: 3
---------------------------
Press any key to continue . . .