fork(1) 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 <unordered_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. // Hash for using pair as key for unordered map.
  25. struct PairHash {
  26. 	size_t operator () (const state &e) const {
  27. 		return (e.first * 31 + e.second);
  28. 	}
  29. };
  30.  
  31. unordered_map<state, int, PairHash> memo;
  32.  
  33. // index: index of the current item being considered in the 'items' vector.
  34. // capacity: capacity remaining in the knapsack.
  35. int knapsack(int index, int capacity) {
  36. 	if (index == N || capacity == 0)  // base cases of recursion.
  37. 		return 0;
  38. 	state cs = state(index, capacity);  // current state of the problem.
  39. 	if (memo.count(cs))  // if state already visited, return its value.
  40. 		return memo[cs];
  41. 	int newcap = capacity - items[index].size;   // new capacity if current item is chosen.
  42. 	int xa = -INF, xb;  // just variables for store the recursive calls result.
  43. 	xb = knapsack(index + 1, capacity);  // if not to chose the current item.
  44. 	if (newcap >= 0)  // if current item fits in the current remaining capacity:
  45. 		xa = knapsack(index + 1, newcap) + items[index].value;  // value if chose the current item.
  46. 	int res = max(xa, xb);  // memoize and return the maximum of both possible choices.
  47. 	memo[cs] = res;
  48. 	return res;
  49. }
  50.  
  51.  
  52. int main() {
  53. 	ios_base::sync_with_stdio(false);
  54. 	cin.tie(NULL);
  55.  
  56. 	int S;
  57. 	cin >> S >> N;
  58. 	items = vector<Item>(N);
  59. 	for (int i = 0; i < N; i++) {
  60. 		cin >> items[i].size >> items[i].value;
  61. 	}
  62. 	cout << knapsack(0, S) << "\n";
  63.  
  64. 	return 0;
  65. }
  66.  
Success #stdin #stdout 4.4s 222736KB
comments (?)
stdin
copy 
2000 2000
99 13
25 15
97 54
19 100
69 82
87 50
25 65
84 9
6 2
93 94
90 22
30 91
7 21
19 74
21 7
84 30
26 50
46 100
87 87
47 98
16 62
88 45
54 3
3 25
53 93
8 43
76 41
98 83
31 24
39 74
54 95
42 15
34 25
90 27
1 99
52 34
66 82
99 62
70 6
85 43
72 94
2 100
75 33
79 58
46 39
57 3
91 43
79 15
72 53
62 87
15 51
23 69
17 100
8 34
54 32
64 53
88 85
66 88
85 62
12 1
93 58
42 85
37 54
76 33
64 42
71 48
91 55
17 58
70 79
27 34
89 73
65 74
16 74
46 21
23 85
74 67
30 18
14 81
39 34
38 11
49 89
79 90
96 16
31 65
24 76
79 23
28 15
55 80
41 83
80 32
4 100
3 32
61 59
13 88
95 42
94 55
37 40
2 22
58 15
33 24
78 0
24 53
77 43
56 78
46 27
10 37
98 53
77 98
59 96
1 88
85 53
33 31
89 87
30 96
58 0
100 100
58 48
4 8
32 38
95 73
5 48
60 62
6 25
56 23
19 20
22 72
49 70
94 1
61 54
32 3
94 31
13 29
85 56
50 56
44 20
80 2
15 55
49 99
57 87
48 56
2 82
70 52
70 38
21 41
39 90
74 1
91 40
16 77
62 0
49 49
70 72
63 48
8 39
19 34
85 92
30 59
97 84
19 31
70 96
62 98
58 9
65 38
45 93
73 74
39 72
76 46
78 98
22 88
7 72
10 58
59 41
2 54
76 83
45 62
46 38
65 75
81 61
55 20
63 41
63 48
3 58
59 40
60 51
40 89
23 10
14 70
78 36
77 97
97 40
98 44
75 50
39 24
41 58
100 94
79 77
50 55
3 14
19 94
31 63
57 7
89 88
26 90
12 12
89 77
72 37
65 42
56 82
26 11
57 26
33 84
11 24
67 14
82 45
66 2
54 59
11 11
6 47
48 22
36 1
100 94
91 72
82 11
91 23
72 19
24 44
79 21
29 68
96 98
29 48
85 41
57 10
53 53
13 16
59 79
81 28
77 65
3 17
78 63
31 12
80 2
62 72
91 99
42 10
32 27
36 46
64 83
59 57
61 70
66 33
45 3
39 80
3 25
54 31
98 72
82 40
32 13
47 13
69 54
90 15
82 97
24 70
90 49
57 97
34 87
12 69
52 57
89 45
59 11
22 76
56 24
43 89
76 51
37 71
87 81
13 35
64 86
32 70
85 78
65 30
51 49
73 98
97 84
91 2
48 88
30 96
96 100
83 29
22 62
19 53
42 6
13 65
86 90
95 40
62 94
24 93
50 77
78 22
64 62
66 53
27 9
35 69
41 22
70 66
85 75
93 44
63 70
58 4
34 13
41 74
1 100
100 44
94 38
81 58
73 92
94 50
37 17
5 6
70 15
11 4
39 62
18 68
66 12
40 95
88 54
27 100
56 9
22 80
65 87
76 81
81 18
24 100
5 13
52 92
60 43
5 13
15 100
62 57
37 42
52 27
29 87
24 43
75 0
66 92
92 30
38 42
87 78
52 56
100 82
88 27
12 3
75 34
4 34
75 31
83 31
8 86
30 64
74 14
30 0
73 15
86 0
9 19
15 76
57 9
53 17
19 80
68 83
24 92
91 80
20 4
78 62
30 21
64 9
17 88
11 48
74 36
45 59
50 23
32 45
92 32
79 57
79 30
41 89
59 91
87 40
48 26
91 63
9 26
73 65
68 16
68 54
27 36
53 49
73 24
81 54
92 75
40 100
2 77
22 87
52 42
4 24
32 2
10 88
86 63
56 12
12 32
73 41
88 58
80 8
66 25
51 33
16 5
69 63
39 20
83 23
56 11
37 93
26 19
15 83
5 89
61 31
46 92
44 1
67 71
59 60
39 89
85 50
8 29
85 53
2 19
1 39
13 33
91 82
33 96
47 5
48 30
29 95
18 47
15 17
5 32
39 85
70 22
10 67
34 24
3 66
12 44
20 65
60 48
7 26
92 59
42 37
5 58
70 47
11 71
68 66
6 21
8 16
92 29
95 74
24 76
7 84
47 51
83 11
94 73
12 12
50 5
46 33
2 1
59 26
92 1
74 2
31 83
48 63
96 0
45 57
31 91
39 89
6 82
64 48
32 52
66 99
80 27
25 62
68 9
54 28
64 3
67 18
20 53
43 34
12 99
92 66
11 64
97 85
93 64
11 66
99 6
10 10
87 38
92 55
71 53
14 81
71 24
92 97
22 93
49 90
62 31
78 56
62 96
69 20
22 51
48 20
49 54
89 55
91 27
62 83
88 73
95 53
78 52
81 28
22 32
82 78
43 85
83 34
38 42
60 82
34 77
47 47
47 38
61 50
67 98
71 18
37 28
78 44
9 54
61 25
81 39
99 86
56 12
2 69
78 19
89 51
43 31
36 45
51 74
76 66
100 64
97 9
42 79
18 21
95 83
69 59
79 13
73 16
63 63
48 76
100 43
11 15
51 32
12 80
81 53
18 73
4 23
95 50
53 52
54 84
73 50
93 79
15 19
59 78
40 92
52 48
63 72
53 3
82 70
37 24
43 59
80 86
87 58
24 25
24 46
100 73
96 65
16 48
62 62
40 20
77 70
5 55
38 31
27 26
31 12
90 32
15 36
59 48
96 38
1 76
13 28
74 6
32 31
49 23
60 18
1 86
47 53
81 16
23 47
6 73
34 79
17 44
97 38
1 88
27 64
62 6
24 8
3 15
62 71
83 54
54 20
91 67
68 43
49 20
40 30
82 43
32 7
74 68
15 36
61 56
23 15
60 34
81 18
28 88
88 13
47 42
85 64
61 92
5 55
33 92
74 69
94 20
55 16
69 89
71 50
57 6
85 8
82 71
29 2
90 70
14 98
98 92
65 38
69 82
78 2
63 47
15 73
86 8
34 42
23 70
34 14
83 77
72 1
16 50
60 12
87 41
75 25
31 36
100 1
26 38
49 81
16 42
85 69
100 72
96 94
66 5
83 23
27 73
50 1
1 78
82 94
58 72
41 79
13 2
56 52
39 52
91 50
86 39
76 0
51 72
21 92
95 69
60 94
67 7
86 18
46 45
56 69
99 80
7 11
89 74
95 18
44 89
15 12
36 90
50 54
97 18
70 23
19 39
83 89
59 35
9 87
85 68
49 9
59 88
28 0
15 24
62 5
53 51
35 57
53 55
71 3
19 16
7 89
54 34
62 35
69 15
73 86
74 47
86 22
84 75
93 86
26 0
27 21
57 84
73 31
44 37
92 19
71 31
84 62
35 65
27 34
78 21
21 9
59 1
42 72
13 57
92 86
33 46
84 68
30 8
34 75
63 12
94 92
10 75
97 9
24 59
9 34
41 27
58 41
91 34
74 15
90 63
57 53
4 48
37 33
59 35
66 83
76 31
77 76
96 13
60 54
26 14
100 44
98 32
25 10
84 29
67 27
40 51
26 97
19 32
43 21
27 79
80 68
3 97
74 47
59 8
5 81
71 5
30 97
90 7
16 40
6 27
45 35
43 4
38 77
42 18
71 63
95 20
56 68
67 42
14 54
22 45
60 77
26 58
30 46
48 17
67 87
28 45
25 74
25 90
70 28
83 83
49 45
59 14
88 33
57 53
52 32
94 28
71 37
76 90
30 28
76 57
79 96
52 15
44 34
88 94
86 50
54 16
15 73
37 78
94 1
6 33
84 33
68 12
13 100
76 29
84 55
57 70
68 13
87 72
19 40
73 69
65 97
70 64
29 93
58 34
18 56
70 73
70 84
40 8
76 78
80 93
11 48
100 88
22 93
27 17
72 52
43 66
26 36
16 49
85 63
48 57
12 39
100 23
45 56
54 68
73 22
22 35
3 100
91 46
11 30
72 5
48 79
33 38
80 35
67 79
78 72
21 75
38 89
57 73
6 69
83 24
40 18
35 50
100 33
18 20
84 65
66 43
28 52
36 52
100 81
24 40
68 11
6 48
91 61
87 44
23 39
93 64
75 96
45 86
42 15
31 50
47 90
8 32
95 22
99 36
52 17
16 89
65 45
68 15
43 29
67 78
30 99
70 15
19 10
3 48
59 95
67 66
95 20
26 52
7 93
39 72
35 47
43 97
67 73
7 6
88 29
35 33
48 56
31 4
24 29
93 91
99 69
66 38
17 75
96 97
78 90
38 82
42 13
8 71
43 19
54 97
32 85
8 41
94 85
5 5
21 82
56 23
66 62
77 42
69 77
21 17
11 16
12 61
65 4
46 10
23 85
54 54
64 98
77 20
11 49
19 22
41 0
15 20
43 54
84 8
72 15
68 94
12 93
35 60
99 61
71 71
68 4
35 56
67 11
34 43
92 37
18 97
16 10
44 54
18 87
98 19
8 1
25 22
55 75
69 66
64 40
14 88
98 61
44 92
89 71
56 58
71 25
8 74
37 97
49 48
22 47
71 55
56 76
81 28
27 17
28 83
84 14
29 40
47 10
71 51
77 50
36 57
22 98
79 6
53 12
75 56
11 26
33 76
75 47
77 89
72 44
33 2
30 51
8 4
11 94
18 88
13 0
83 55
8 53
2 55
84 3
96 43
26 47
22 5
85 32
2 28
8 10
22 97
35 8
98 6
42 82
11 88
29 75
46 49
98 52
31 20
86 8
57 85
4 58
81 37
86 54
25 88
11 18
95 70
21 72
2 39
46 17
60 99
37 86
63 48
63 17
67 51
64 62
6 58
32 1
37 26
11 99
36 80
47 34
67 84
27 91
31 89
43 19
75 8
66 26
8 74
16 87
92 50
87 29
33 79
45 38
37 95
28 17
51 95
18 6
17 46
11 78
89 98
98 96
46 19
76 67
69 67
45 53
7 88
1 98
60 56
28 88
25 63
73 42
38 31
93 26
48 61
78 17
66 58
10 76
62 4
94 71
53 87
46 98
64 99
41 42
95 14
40 28
89 26
1 9
79 67
70 83
57 12
1 48
96 52
95 5
35 0
69 72
37 56
46 97
24 49
15 48
54 44
17 92
80 53
23 34
21 92
100 54
7 87
59 90
100 8
57 53
34 65
80 77
52 64
13 24
57 82
71 75
18 17
84 39
78 51
37 51
80 41
42 81
64 52
78 24
77 29
8 56
56 94
85 57
26 86
51 91
40 94
6 45
78 29
75 28
7 26
72 46
76 96
17 22
35 79
40 49
80 15
25 87
18 79
72 91
76 45
57 82
100 46
79 81
90 18
1 70
44 19
46 48
58 73
23 75
48 64
52 69
60 95
84 71
45 61
63 21
91 85
30 48
86 12
11 96
97 36
88 28
20 33
52 82
76 65
34 83
64 38
31 83
69 27
68 47
17 84
54 41
63 67
43 0
98 52
46 6
2 53
48 63
24 88
68 50
61 38
31 18
25 40
84 1
51 63
23 8
97 80
32 55
12 53
92 66
81 42
35 62
82 23
31 91
52 77
54 73
65 39
94 0
50 88
86 31
1 37
16 40
17 58
98 61
76 95
9 13
77 92
28 93
24 3
20 49
81 28
20 98
72 10
79 57
8 17
65 75
68 26
64 24
87 12
21 9
89 2
19 70
6 36
42 89
4 69
62 42
61 14
59 96
10 37
41 60
55 44
44 11
18 33
84 82
82 47
19 37
16 43
18 35
35 59
65 23
72 91
20 88
99 26
35 60
38 8
6 96
51 77
68 53
42 87
61 13
90 3
6 34
76 63
78 69
97 85
96 15
41 68
71 97
30 50
62 14
54 60
88 72
31 67
97 41
77 93
56 81
45 55
26 78
11 96
55 86
87 51
41 2
2 61
98 67
39 88
100 36
46 60
32 46
85 64
50 34
74 28
78 14
33 57
65 47
47 1
5 16
89 17
47 82
9 33
31 58
52 20
34 1
70 16
66 71
58 59
7 9
62 84
81 86
38 44
1 38
100 41
13 99
82 4
86 49
7 45
70 65
12 48
32 5
78 96
72 23
28 45
21 96
66 63
6 75
10 73
10 73
9 83
13 96
73 48
45 41
27 5
69 68
17 71
51 91
47 58
13 20
88 71
5 79
21 52
97 87
57 86
90 77
66 99
6 100
60 69
35 16
34 89
58 86
68 32
82 34
84 1
98 40
36 58
7 18
78 98
73 75
40 67
72 80
77 22
43 26
16 66
20 37
46 88
17 6
9 58
98 5
45 65
10 88
11 83
50 79
34 20
82 91
34 63
32 14
22 18
46 24
45 93
73 33
41 0
60 29
53 88
80 18
42 72
14 53
33 79
15 18
43 21
77 61
26 70
82 48
15 33
47 24
32 93
25 68
91 70
87 80
56 65
98 66
29 32
5 14
25 5
22 78
45 43
55 5
3 70
65 3
13 32
2 37
69 74
94 64
32 87
61 76
64 80
43 52
18 50
75 74
30 9
67 93
96 88
18 31
97 56
7 63
28 1
60 68
48 81
80 99
31 10
71 52
73 94
31 19
23 45
35 83
87 100
20 18
92 28
21 23
40 81
51 91
83 52
17 33
48 58
76 17
80 87
44 23
60 11
25 47
61 94
52 49
96 33
40 10
90 87
88 15
7 5
64 16
64 2
27 21
17 35
59 19
13 95
74 54
94 95
38 86
61 18
83 11
49 41
63 68
33 53
23 31
65 4
54 4
51 38
67 72
1 73
88 17
24 96
76 70
66 92
27 48
91 65
46 47
79 62
37 6
26 75
92 95
52 87
94 77
99 10
95 61
34 67
56 95
31 68
88 33
91 67
65 9
43 11
78 98
61 81
99 75
58 20
58 40
5 6
30 67
57 80
96 64
45 82
66 57
11 46
94 69
62 67
40 84
100 91
44 55
4 73
37 36
89 72
81 21
61 51
66 60
75 94
90 34
67 77
83 13
95 24
91 9
34 36
17 13
55 0
68 17
18 26
83 24
6 11
9 76
96 54
30 54
31 73
19 7
57 82
11 69
69 94
81 34
49 87
73 27
41 41
73 42
22 50
6 60
56 47
9 69
60 1
50 58
3 68
92 77
27 78
74 78
24 100
14 93
29 66
9 31
2 68
56 17
36 79
26 82
72 37
85 31
64 66
8 81
87 50
32 1
73 82
48 21
85 87
8 58
17 14
30 7
96 47
8 100
19 52
68 98
2 53
80 100
85 45
21 21
13 57
25 13
27 14
13 94
36 67
50 94
21 22
65 5
54 40
73 25
90 86
98 89
11 14
5 89
10 56
14 30
89 87
89 50
27 4
60 53
12 64
98 35
25 92
50 14
20 44
85 60
47 73
19 86
28 28
1 22
95 15
75 81
15 71
59 6
37 9
98 35
92 40
2 59
92 24
10 83
8 32
28 44
11 22
89 34
91 35
83 43
21 92
55 7
23 53
12 47
99 17
99 13
34 28
84 92
60 58
29 40
17 43
53 83
93 41
2 65
69 15
25 61
6 1
82 57
43 55
79 97
54 62
34 56
44 7
71 37
69 62
86 35
14 31
87 35
46 46
28 53
34 66
22 24
47 62
54 92
87 59
35 7
22 4
86 14
14 29
98 24
97 59
24 78
84 2
100 38
49 31
71 57
93 3
93 77
59 41
13 30
97 20
79 99
71 20
23 0
44 68
57 31
54 18
38 79
15 35
58 10
23 59
17 1
42 54
57 21
47 85
92 11
21 1
23 50
36 88
51 98
80 60
81 60
13 83
5 49
3 24
23 26
33 53
9 30
20 23
55 19
82 35
65 9
91 10
6 46
30 4
70 55
20 54
48 96
74 68
100 94
3 37
28 21
22 30
41 49
62 21
57 71
54 91
41 21
3 31
56 87
47 71
11 0
47 14
45 61
43 83
82 99
13 100
27 62
34 97
37 23
86 41
71 77
19 69
93 95
98 15
81 79
61 41
20 50
69 21
8 69
46 67
60 48
95 99
7 81
14 17
55 56
14 27
99 43
94 62
22 78
37 80
91 90
70 81
98 7
64 81
87 23
1 57
61 29
75 2
89 47
62 96
83 3
51 50
39 29
6 26
70 89
46 43
78 36
53 7
20 26
23 72
53 16
94 14
70 95
79 58
65 12
7 13
34 79
46 33
67 14
90 63
6 47
28 35
12 46
51 72
1 43
58 48
35 21
14 92
86 97
59 2
71 73
67 22
64 100
98 17
43 82
93 86
36 26
64 70
26 55
30 2
14 62
93 10
17 82
35 60
59 5
1 41
7 99
38 37
29 62
58 24
20 10
59 9
51 93
80 90
63 77
70 67
95 12
71 17
54 44
32 80
58 11
12 46
73 64
48 82
33 58
85 85
15 44
60 78
52 67
36 30
29 24
94 50
59 6
3 7
91 75
100 57
45 15
83 73
34 12
75 59
96 48
63 83
7 51
4 54
73 87
10 86
10 33
26 21
12 56
11 54
17 29
69 18
77 18
7 74
53 42
17 69
68 26
20 51
41 42
66 39
9 25
37 52
56 18
75 24
52 90
6 82
12 68
33 16
2 39
84 94
54 63
66 31
31 59
3 98
34 96
60 20
20 48
53 2
85 33
90 10
21 72
15 46
6 18
22 1
14 16
56 77
86 81
26 7
26 54
94 75
31 95
67 38
83 11
44 70
54 6
46 0
24 61
83 9
9 85
59 25
24 47
100 64
87 72
55 51
56 64
97 56
69 88
68 26
17 75
41 56
20 86
30 26
66 55
28 65
46 88
94 50
27 44
12 84
89 32
77 45
6 39
75 20
28 3
73 28
66 76
6 17
86 69
58 60
29 47
63 43
98 15
68 10
92 72
18 21
73 10
58 78
5 60
19 10
36 11
45 23
75 92
27 81
79 67
17 13
84 57
41 55
74 59
32 54
10 16
21 11
19 0
79 30
4 63
7 90
83 39
13 69
10 90
95 15
31 98
67 10
33 20
90 20
80 44
81 67
97 77
34 50
77 48
64 54
82 48
1 54
3 32
69 99
56 88
79 68
50 59
59 58
54 51
52 48
7 86
19 88
stdout
copy 
15809
https://ideone.com/raHyug
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!