Advertisement
WONGDEEM

Untitled

Apr 27th, 2019
113
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main() {
  4.     int n,v;
  5.     cin >> n >> v;
  6.     int coins[n];
  7.     int value[v+1];
  8.     for (int i=0;i<n;i++) {
  9.         cin >> coins[i];
  10.     }
  11.     for (int i=0;i<v+1;i++) {
  12.         value[i] = INT_MAX;
  13.     }
  14.     sort(coins,coins+n);
  15.     value[0] = 0;
  16.     for (int i=1;i<v+1;i++) {
  17.         for (int j=0;j<n;j++) {
  18.             if (coins[j] <= i && value[i-coins[j]] !=INT_MAX && value[i-coins[j]] + 1 < value[i]) {
  19.                 value[i] = value[i-coins[j]]+1;
  20.             }
  21.         }
  22.     }
  23.     if (value[v] == INT_MAX) {
  24.         cout << -1;
  25.     } else {
  26.         cout << value[v];
  27.     }
  28. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement