apl-mhd

knapsack coin change

Sep 21st, 2021
545
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. int M[100];
  5. int S[100];
  6. int sum(int c[], int n, int coinSize){
  7.  
  8.    if(M[n] == -1){
  9.  
  10.         int minval=9999, coinval =-1;
  11.  
  12.         for(int i=0; i<coinSize; i++){
  13.  
  14.             if(c[i]<=n){
  15.  
  16.                 int tval = 1+sum(c, n-c[i],coinSize);
  17.  
  18.                     if(tval<minval) {
  19.                         minval = tval;
  20.                         coinval = c[i];
  21.                     }
  22.             }
  23.         }
  24.  
  25.         M[n] = minval;
  26.         S[n] = coinval;
  27.     }
  28.  
  29.     return M[n];
  30. }
  31.  
  32. int main() {
  33.    
  34.    
  35.  
  36.     M[0]=0;
  37.  
  38.     for(int i=1; i<100; i++)
  39.         M[i]=-1;
  40.     int coins[]= {2,4,5,6,8};
  41.     //x = how many want you take input
  42.     //for(i=0; i<x){
  43.         //take input  coins[i]
  44.     //}
  45.    
  46.     int coinSize = 5; //arraysize
  47.     int n=0;
  48.    
  49.      int result = sum(coins, n, coinSize);
  50.    
  51.      if(result == 9999){
  52.         cout<<"False"<<endl;
  53.      }
  54.      else if(result == 0){
  55.          cout<<"True {}"<<endl;
  56.      }
  57.      else{
  58.          
  59.          cout<<"True{";
  60.      
  61.  
  62.     int end = n;
  63.     while(end !=0 ){
  64.  
  65.          cout<<S[end]<<",";
  66.          //cout<<S[end]<<" ";
  67.          end -=S[end];
  68.          
  69.    }
  70.     cout<<"}";
  71.      
  72.          
  73.      }
  74.     return 0;
  75. }
RAW Paste Data