fork download
copy 
  1. #include <iostream>
  2. #include <climits>
  3. using namespace std;
  4.  
  5. int minCoins(int coins[], int n, int V) {
  6.     int dp[V + 1];
  7.  
  8.     // Base case
  9.     dp[0] = 0;
  10.  
  11.     // Initialize all table values as Infinite
  12.     for (int i = 1; i <= V; i++)
  13.         dp[i] = INT_MAX;
  14.  
  15.     // Compute minimum coins required for all
  16.     // values from 1 to V
  17.     for (int i = 1; i <= V; i++) {
  18.         // Go through all coins smaller than i
  19.         for (int j = 0; j < n; j++)
  20.             if (coins[j] <= i) {
  21.                 int sub_res = dp[i - coins[j]];
  22.                 if (sub_res != INT_MAX && sub_res + 1 < dp[i])
  23.                     dp[i] = sub_res + 1;
  24.             }
  25.     }
  26.     return (dp[V] == INT_MAX) ? -1 : dp[V];
  27. }
  28.  
  29. int main() {
  30.     int T;
  31.     cin >> T;
  32.     while (T--) {
  33.         int V, N;
  34.         cin >> V >> N;
  35.         int coins[N];
  36.         for (int i = 0; i < N; i++)
  37.             cin >> coins[i];
  38.         cout << minCoins(coins, N, V) << endl;
  39.     }
  40.     return 0;
  41. }
  42.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
1
7 2
2 1
stdout
copy 
4
https://ideone.com/oOqoav
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!