If u don't want the concepts or if u already have knowledge of greedy and DP design techniques skip The first two paragraphs.
There are many variations of Knapsack problem, fractional knapsack and Integer knapsack being the most prominent ones. The fractional knapsack is solved using greedy Algorithm design technique since it follows the matroid theory, while the integer knapsack is solved using dynamic programming. Both dynamic and greedy algorithm design techniques are used to solve combinatorial optimization problems. Study CRS(coremen) book for further details or you can take a look of the data structure and algorithm by Narashimha Karumanchi...See the dynamic programming chapter.
Coming to ur problem it's better to call it coin exchange problem. Although it is same as knapsack. Since In ur problem as many coins of one type can be used, it will be solved using Greedy Design technique. (It can also be solved using dynamic prog. technique. In fact all problem which can be solved using greedy, can be solved using dynamic since greedy algorithm design technique applies to a problem which are having a property viz. property of following matroid theory... Also it must follow optimal Substructure And Overlapping problem properties for being solvable by DP. The story is long, So directly coming to the solution. Here is the pseudocode of the solution.
Algorithm:
Select the coin which is having largest value(called denomination) but is less than the sum S keep selecting coin of this denomination until the sum S becomes less than this coin value REPEAT the above procedure until sum S becomes 0 or You end up with No coin denomination whose v value is less than sum S.
Code: Assuming the coinDenominationsArr is sorted in decreasing order
int coinExchange(int S, int coinDenominationsArr[ ], int N ){
int remainSum=S;
int i=0, no_of_coins_required=0;
while(remainSum > 0 && i < N){
if ( coinDenominationsArr[i] < =remainSum)
no_of_coins_required += remainSum / coinDenominationsArr[i];
i++;
}
if(remainSum > 0 )
return -1; // Not Possible
return no_of_coins_required;
}
Now the problem Starts here:
Consider an example:-
the coin denominations are { 5,4,1} and the sum S = 28
Following the greedy strategy as described above :
The number of coins required = 8 since following the greedy approach mentioned above. while u can easily find out that 7 is the optimal no. of coins. So the solution is Dynamic programming where we explore all possible combinations of coin and figure out which possible combination is having less count. ( You can easily see that finding out every possible combination has many overlapping instances.
Correct Solution:
Read the article: http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
I didn't gave the DP answer here since the article mentioned is very good and that will easily make u understand what's going on. Hope this helps:)
