top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

The Knapsack problem.

+2 votes
705 views

Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way that they sum up to S.

posted Apr 29, 2014 by Muskan

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
follow any standard algo book

1 Answer

+3 votes
 
Best answer

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:)

answer May 1, 2014 by Prakash
Similar Questions
+1 vote

Please help me to solve the Knapsack problem using greedy algorithms.

  Profit Weight    
1) 30    10
2) 50    5
3) 20    12
4) 70    40
5) 90    15

The knapsack size is 50. Make the selection criteria based on : min weight, max profit and Ratio.

+5 votes

Josephus Problem talks about a problem where there are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

...