Solving Coin Change using knapsack . Reference : Another Knapsack Hackerrank CodeAgon

Question

The problem is fairly simple and straight .However i cannot solve it exclusively using dp knapsack style . I have solution for that but since the number of coins in each denomination here is limited (in this question it's )it's creating a problem . I want to arrive at a 2d recurrence that i can use to implement the knapsack . My actual solution which runs fine goes below :

#include<iostream> 
using namespace std ; 
int main ()
{ int flag ;
  int N,i ; 
  int sum ; 
  int counter ; 
  while (cin >> N >>sum )
  {  
    counter = 0; 
    flag= 0 ;
    int count =0; 
    for( i = N ; i>=1;i--){
      count += i ;
      counter++;
      if (count >sum){
      count-=i ;
      counter -- ;  
      }
      if(count == sum){
      flag = 1 ;
      break ; 
      }
      }
 if (flag==1)
 cout << counter<<"\n" ;
 else cout <<-1<<"\n" ;
}
return 0 ;
}

user3820950 · Accepted Answer · 2015-09-30 10:48:40Z

Dynamic programming solution is not required for the problem as the constraint are quite high.A simple greedy approach would work fine.

The algorithm works as follows:

If the sum of all the values form 1 to n is less than m then you cannot pay m coins because even after using all the n coins you have money remaining to be paid.
If the sum of all the values form 1 to n is greater than or equal to m then you can definitely pay because you have enough coins.
Since you have to minimize the number of coins to be given you consecutively pick coins that have the maximum value until your m become zero and you need to only keep track of number of coins that you have picked.

Below is the code that implements the above algorithm

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    if (m > (n * (n + 1) / 2)) {
        //if sum of all coins form 1 to n is less than m
        cout << "-1";
    } else {
        int cnt = 0;
        while (m != 0) {
            if (n >= m) {
                m = 0;
            } else {
                m -= n;
                --n;
            }
            ++cnt;
        }
        cout << cnt;
    }
    return 0;
}

Collectives™ on Stack Overflow

Solving Coin Change using knapsack . Reference : Another Knapsack Hackerrank CodeAgon

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related