top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Coin Denomination Problem Solution in polynomial time

+3 votes
497 views

Standard Coin denomination problem is as follows

coin set = {1,2,5,10 ... } - each coin count is unlimited
find count of possible combinations of coins to create N Rs

This problem can either be done using backtracking or dynamic programming

Now My requirement added a factor where max count of each coin is given e.g.

{ (1, 10), (2, 5), (5, 4), (10, 100) } where (n,m) denotes m coins are of each n Rupees.

This can be done using backtracking by an addition check while inserting element to stack but this takes exponential time. Can somebody provides solution using dynamic programming ?

thanks in advance..

posted Dec 2, 2013 by Pankaj Agarwal

Looking for an answer?  Promote on:
Facebook Share Button Twitter Share Button LinkedIn Share Button

Similar Questions
+1 vote
Coin Change Problem: minimum number of coins required to form sum S.

Given an array of denominations and array Count , find minimum number of coins required to form sum S.

for example: 

  coins[]={1,2,3};
  count[]={1,1,3};

i.e we have 1 coin of Rs 1 , 1 coin of Rs 2 , 3 coins of Rs 3.

Now if we input S = 6 then output should be 2 with possible combination : 3+3 = 6

+2 votes
How to solve this problem using c++ with operations in log complexities for both update and count?

suppose we have an array of N natural numbers and asks him to solve the following queries:-
Query a:- modify the element present at index i to x.
Query b:- count the number of even numbers in range l to r inclusive.
Query c:- count the number of odd numbers in range l to r inclusive.

input:
First line of the input contains the number N. Next line contains N natural numbers.Next line contains an integer Q followed by Q queries.
a x y - modify the number at index x to y.
b x y - count the number of even numbers in range l to r inclusive.
c x y - count the number of odd numbers in range l to r inclusive.
I tried to solve using simple arrays but it isn't doing well for big constraints so I thought to use other DS with efficient algorithm so please explain appropriate algorithm.Thanks in advance.

+1 vote
Knapsack problem with size 50?

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.

...