fork download
copy 
  1. /*
  2. 0-1 Knapsack Problem
  3. */
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10.  
  11. vector<pair<ll, ll>> weightValues;
  12. ll n, maxWeight;
  13.  
  14. ll maxVal(vector<vector<ll>> &dp, ll startInd, ll maxWt) {
  15. 	if (startInd >= n || maxWt <= 0) return 0;
  16.  
  17. 	if (dp[startInd][maxWt] != -1) return dp[startInd][maxWt];
  18.  
  19. 	if (weightValues[startInd].first > maxWt) {
  20. 		return dp[startInd][maxWt] = maxVal(dp, startInd + 1, maxWt);
  21. 	}
  22.  
  23. 	return dp[startInd][maxWt] = max(weightValues[startInd].second + maxVal(dp, startInd + 1, maxWt - weightValues[startInd].first),
  24. 									 maxVal(dp, startInd + 1, maxWt));
  25.  
  26. }
  27.  
  28. int main() {
  29. 	ll x, y;
  30. 	vector<ll> input;
  31.  
  32.  
  33. 	scanf("%lld %lld", &maxWeight, &n);
  34. 	for (ll i = 0; i < n; ++i) {
  35. 		scanf("%lld %lld", &x, &y);
  36. 		weightValues.emplace_back(x, y);
  37. 	}
  38.  
  39. 	sort(weightValues.begin(), weightValues.end(), [](pair<ll, ll> a, pair<ll, ll> b) {
  40. 		return a > b;
  41. 	});
  42.  
  43. 	vector<vector<ll>> dp(n, vector<ll> (maxWeight + 1, -1));
  44.  
  45. 	printf("%lld", maxVal(dp, 0, maxWeight));
  46.  
  47. 	return 0;
  48. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/z8SuKK
problem KNAPSACK, based on SPOJ submission 22472231 (CPP14), 2018-10-09 16:47:05
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!