Advertisement
Josif_tepe

Untitled

Dec 7th, 2021
176
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. int n;
  5. int cost[105], weight[105];
  6. long long dp[101][100001];
  7. long long rek(int at, int weight_left) {
  8.     if(at == n or weight_left == 0) {
  9.         return 0;
  10.     }
  11.     if(dp[at][weight_left] != -1) {
  12.         return dp[at][weight_left];
  13.     }
  14.     long long maks = -1e15;
  15.     maks = max(maks, rek(at + 1, weight_left)); // sto ako ne go zememe ovoj element
  16.    
  17.     if(weight_left - weight[at] >= 0) {
  18.         maks = max(maks, rek(at + 1, weight_left - weight[at]) + cost[at]); // sto ako go zememe ovoj element
  19.     }
  20.     dp[at][weight_left] = maks;
  21.     return maks;
  22. }
  23. int main()
  24. {
  25.     cin >> n;
  26.     int max_weight;
  27.     cin >> max_weight;
  28.     for(int i = 0; i < n; i++) {
  29.         cin >> weight[i] >> cost[i];
  30.     }
  31.    
  32.    
  33.     for(int i = 0; i < n; i++) {
  34.         for(int j = 0; j <= max_weight; j++) {
  35.             dp[i][j] = -1;
  36.         }
  37.     }
  38.     cout << rek(0, max_weight) << endl;
  39.        return 0;
  40. }
  41.  
  42.  
  43.  
  44.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement