fork download
copy 
  1. // https://w...content-available-to-author-only...j.com/problems/KNAPSACK/
  2. // Top-down, dynamic programming knapsack implementation.
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <utility>
  6. #include <vector>
  7. #include <map>
  8. using namespace std;
  9.  
  10. #define INF 1e9
  11.  
  12. // State of the problem. First: index of current element on items vector. Second: capacity remaining.
  13. typedef pair<int, int> state;  
  14.  
  15. struct Item {
  16. 	int size;
  17. 	int value;
  18. };
  19.  
  20. vector<Item> items;
  21.  
  22. int N;
  23.  
  24. map<state, int> memo;
  25.  
  26. // index: index of the current item being considered in the 'items' vector.
  27. // capacity: capacity remaining in the knapsack.
  28. int knapsack(int index, int capacity) {
  29. 	if (index == N || capacity == 0)  // base cases of recursion.
  30. 		return 0;
  31. 	state cs = state(index, capacity);  // current state of the problem.
  32. 	if (memo.count(cs))  // if state already visited, return its value.
  33. 		return memo[cs];
  34. 	int newcap = capacity - items[index].size;   // new capacity if current item is chosen.
  35. 	int xa = -INF, xb;  // just variables for store the recursive calls result.
  36. 	xb = knapsack(index + 1, capacity);  // if not to chose the current item.
  37. 	if (newcap >= 0)  // if current item fits in the current remaining capacity:
  38. 		xa = knapsack(index + 1, newcap) + items[index].value;  // value if chose the current item.
  39. 	int res = max(xa, xb);  // memoize and return the maximum of both possible choices.
  40. 	memo[cs] = res;
  41. 	return res;
  42. }
  43.  
  44.  
  45. int main() {
  46. 	ios_base::sync_with_stdio(false);
  47. 	cin.tie(NULL);
  48.  
  49. 	int S;
  50. 	cin >> S >> N;
  51. 	items = vector<Item>(N);
  52. 	for (int i = 0; i < N; i++) {
  53. 		cin >> items[i].size >> items[i].value;
  54. 	}
  55. 	cout << knapsack(0, S) << "\n";
  56.  
  57. 	return 0;
  58. }
  59.  
Success #stdin #stdout 0s 4300KB
comments (?)
stdin
copy 
4 5
1 8
2 4
3 0
2 5
2 3
stdout
copy 
13
https://ideone.com/PANnMG
language:
C++14 (gcc 8.3)
created:
4 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!