cpp/test.cpp at main · jayantsingh-22/cpp · 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

#include <bits/stdc++.h>
using namespace std;

int minServerLoads(int n, vector<int>& servers)
{

	int totalLoad = 0;
	for(int i : servers) totalLoad += i;

	int requiredLoad = totalLoad / 2;


	vector<vector<int>> dp(n + 1,
	vector<int>(requiredLoad + 1, 0));

	for(int i = 1; i < n + 1; i++)
	{
		for(int j = 1; j < requiredLoad + 1; j++)
		{


			if (servers[i - 1] > j)
				dp[i][j] = dp[i - 1][j];


			else
				dp[i][j] = max(dp[i - 1][j],
						servers[i - 1] +
						dp[i - 1][j - servers[i - 1]]);
		}
	}

	return totalLoad - 2 * dp[n][requiredLoad];
}

// Driver Code
int main()
{
	int N = 5;

	vector<int> servers = { 1, 2, 3, 4, 5 };

	cout << (minServerLoads(N, servers));
}