Facebook
From a, 9 Months ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 383
  1. vector<vector<int>> dp(102, vector<int>(102, -1)); // Using a vector for memoization
  2.  
  3. int minCoinsMemo(int coins[], int sum, int n, vector<int>& chosenCoins) {
  4.     if (sum == 0) return 0;
  5.     if (n == 0 || sum < 0) return INT_MAX; // Return a large value for invalid cases
  6.  
  7.     if (dp[n][sum] != -1) return dp[n][sum];
  8.  
  9.     if (coins[n - 1] <= sum) {
  10.         dp[n][sum] = min(minCoinsMemo(coins, sum, n - 1, chosenCoins), 1 + minCoinsMemo(coins, sum - coins[n - 1], n, chosenCoins));
  11.     } else {
  12.         dp[n][sum] = minCoinsMemo(coins, sum, n - 1, chosenCoins);
  13.     }
  14.  
  15.         return dp[n][sum];
  16. }
  17.  
  18. void Print(int coins[],int n, int sum, vector<int> &chosenCoins;){
  19.     int i = n;
  20.         int j = sum;
  21.         while (i > 0 && j > 0) {
  22.             if (dp[i][j] == dp[i - 1][j]) {
  23.                 i--;
  24.             } else {
  25.                 cout<<coins[i - 1]<<' ';
  26.                 j -= coins[i - 1];
  27.             }
  28.         }
  29. }
  30.  
  31. int main() {
  32.     int sum = 7;
  33.     int coins[] = {1, 2, 5};
  34.     vector<int> chosenCoins;
  35.     int n = sizeof(coins) / sizeof(coins[0]);
  36.  
  37.     int result = minCoinsMemo(coins, sum, n, chosenCoins);
  38.  
  39.     if (result == INT_MAX) {
  40.         cout << "It's not possible to make the sum " << sum << " using the given coins." << endl;
  41.     } else {
  42.         cout << "Minimum number of coins required to make the sum " << sum << " is: " << result << endl;
  43.     }
  44.    
  45.     Print(coins, n, sum, chosenCoins);
  46.    
  47.    
  48.  
  49.     return 0;
  50. }