Guest User

Knapsck - 1

a guest
May 28th, 2020
192
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 105;
  5. const int W = 1e5 + 5;
  6. int w[N], v[N];
  7. int dp[N][W];
  8. int n, wt;
  9.  
  10. int dynamic(int pos, int we)
  11. {
  12.  
  13. if (we > wt)
  14. return INT_MIN;
  15. if (pos >= n)
  16. return 0;
  17. if (dp[pos][we] != -1)
  18. return dp[pos][we];
  19. int ans;
  20. ans = max(dynamic(pos + 1, we + w[pos]) + v[pos], dynamic(pos + 1, we));
  21. dp[pos][we] = ans;
  22. return ans;
  23. }
  24.  
  25. int main() {
  26. cin >> n >> wt;
  27. memset(dp,-1,sizeof(dp));
  28. for (int i = 0; i < n; i++)
  29. cin >> w[i] >> v[i];
  30. cout << dynamic(0, 0);
  31. }
RAW Paste Data