fork download
copy 
  1. /*
  2. 0-1 Knapsack Problem
  3. https://w...content-available-to-author-only...f.com/problems/KNAPSACK
  4. */
  5.  
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11.  
  12. vector<pair<ll, ll>> weightValues;
  13. ll n, maxWeight;
  14.  
  15. ll maxVal(vector<vector<ll>> &dp, ll startInd, ll maxWt) {
  16. 	if (startInd >= n || maxWt <= 0) return 0;
  17.  
  18. 	if (dp[startInd][maxWt] != -1) return dp[startInd][maxWt];
  19.  
  20. 	if (weightValues[startInd].first > maxWt) {
  21. 		return dp[startInd][maxWt] = maxVal(dp, startInd + 1, maxWt);
  22. 	}
  23.  
  24. 	return dp[startInd][maxWt] = max(weightValues[startInd].second + maxVal(dp, startInd + 1, maxWt - weightValues[startInd].first),
  25. 									 maxVal(dp, startInd + 1, maxWt));
  26.  
  27. }
  28.  
  29. int main() {
  30. 	ll x;
  31. 	vector<ll> input;
  32.  
  33.  
  34. 	scanf("%lld %lld", &maxWeight, &n);
  35. 	for (ll i = 0; i < 2*n; ++i) {
  36. 		scanf("%lld", &x);
  37. 		input.emplace_back(x);
  38. 	}
  39. 	for (ll i = 0; i < n; ++i) {
  40. 		weightValues.emplace_back(input[i + n], input[i]);
  41. 	}
  42.  
  43. 	sort(weightValues.begin(), weightValues.end(), [](pair<ll, ll> a, pair<ll, ll> b) {
  44. 		return a > b;
  45. 	});
  46.  
  47. 	vector<vector<ll>> dp(n, vector<ll> (maxWeight + 1, -1));
  48.  
  49. 	printf("%lld", maxVal(dp, 0, maxWeight));
  50.  
  51. 	return 0;
  52. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TlAzrj
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!