CodingExcercises/KnapSack_0_1.cpp at master · madhu90/CodingExcercises · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>

// QUESTION: https://www.techiedelight.com/0-1-knapsack-problem/

class Knapsack
{
private:
	int targetWt;
	std::unordered_map<std::string, int> map;
	const std::vector<int>& wts;
	const std::vector<int>& values;

public:
	Knapsack(int W, const std::vector<int>& w, const std::vector<int>& v)
		: targetWt(W), wts(w), values(v)
	{

	}

	int doExponential()
	{
		std::cout << "Exponential solution to 0-1 Knapsack" << std::endl;
		return doExponentialHelper(wts.size() - 1, targetWt);
	}

	int doTopDown()
	{
		std::cout << "DP: Top-down solution to 0-1 Knapsack" << std::endl;
		return doTopDownHelper(wts.size() - 1, targetWt);
	}

	int doBottomUp()
	{
		std::cout << "DP: Bottom-up solution to 0-1 Knapsack" << std::endl;
		std::vector<std::vector<int>> lookup(wts.size() + 1, std::vector<int>(targetWt+ 1, 0));

		for (int i = 1; i < lookup.size(); ++i) {
			for (int j = 1; j < lookup[i].size(); ++j) {
				if (wts[i - 1] > j)
				{
					lookup[i][j] = lookup[i - 1][j];
				} else {
					lookup[i][j] = std::max(lookup[i - 1][j], values[i - 1] + lookup[i - 1][j - wts[i - 1]]);
				}
			}
		}

		return lookup[wts.size()][targetWt];
	}

private:
	int doTopDownHelper(int curr_index, int total_wt)
	{
		if (curr_index < 0 || total_wt == 0)
			return 0;

		std::string key = std::to_string(curr_index) + "_" + std::to_string(total_wt);

		if (map.find(key) == map.end())
		{
			// If you can include the current element, then return the max of including
			// and excluding it
			if (total_wt - wts[curr_index] >= 0)
			{
				int include = values[curr_index] + doTopDownHelper(curr_index - 1, total_wt - wts[curr_index]);
				int exclude = doTopDownHelper(curr_index - 1, total_wt);
				map[key] = std::max(include, exclude);
			} else {
				// If you can't include the current element, find the maximum by excluding it
				map[key] = doTopDownHelper(curr_index - 1, total_wt);
			}
		}

		return map[key];
	}

	int doExponentialHelper(int curr_index, int total_wt)
	{
		if (curr_index < 0 || total_wt == 0)
			return 0;

		// If you can include the current element, then return the max of including
		// and excluding it
		if (total_wt - wts[curr_index] >= 0)
		{
			int include = values[curr_index] + doExponentialHelper(curr_index - 1, total_wt - wts[curr_index]);
			int exclude = doExponentialHelper(curr_index - 1, total_wt);
			return std::max(include, exclude);
		} else {
			// If you can't include the current element, find the maximum by excluding it
			return doExponentialHelper(curr_index - 1, total_wt);
		}
	}
};

int main()
{
	const std::vector<int> wt{ 1, 2, 3, 8, 7, 4 };
	const std::vector<int> v{ 20, 5, 10, 40, 15, 25 };
	int W = 10;
	Knapsack obj(W, wt, v);
	int result1 = obj.doExponential();
	std::cout << "Max value is " << result1 << std::endl;
	int result2 = obj.doTopDown();
	std::cout << "Max value is " << result2 << std::endl;
	int result3 = obj.doBottomUp();
	std::cout << "Max value is " << result3 << std::endl;
	return 0;
}