daily pastebin goal
65%
SHARE
TWEET

Untitled

a guest Jul 11th, 2018 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.  
  5. int main() {
  6.     int i, j;
  7.     int n, k, temp;
  8.     int v[101] = { 0 };
  9.     int dp[10001] = { 0 };
  10.    
  11.     cin >> n >> k;
  12.    
  13.     for (i = 1; i <= n; i++) {
  14.         cin >> v[i];
  15.     }
  16.    
  17.     memset(dp, -1, sizeof(dp));
  18.  
  19.     dp[0] = 0;
  20.    
  21.     for (i = 1; i <= n; i++) {
  22.         for (j = 0; j <= k; j++) {
  23.             if (j >= v[i] && dp[j-v[i]]!= -1) {
  24.                 temp = dp[j - v[i]] + 1;
  25.                 if (dp[j] == -1 || temp < dp[j]) {
  26.                     dp[j] = temp;
  27.                 }
  28.             }
  29.         }
  30.     }
  31.     cout << dp[k] << '\n';
  32.  
  33.  
  34.     return 0;
  35. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top