StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I've solved this problem recently using Dynamic Programming in c++. I have not modified the code to answer your question. But changing some constants and little code should do.</p> <p>The code below reads and solves N problems.Each problem has some people (in your case number of integers) and their weights (integer values). This code tries to split the set into 2 groups with difference being minimum.</p> <pre><code>#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_PEOPLE 100 #define MAX_WEIGHT 450 #define MAX_WEIGHT_SUM MAX_PEOPLE*MAX_WEIGHT using namespace std; int weights[MAX_PEOPLE]; //bool table[MAX_PEOPLE + 1][MAX_WEIGHT_SUM + 1]; bool** create2D(int x, int y) { bool **array = new bool*[x]; for (int i = 0; i < x; ++i) { array[i] = new bool[y]; memset(array[i], 0, sizeof(bool)*y); } return array; } void delete2D(int x, int y, bool **array) { for (int i = 0; i < x; ++i) { delete[] array[i]; } delete[] array; } void memset2D(int x, int y, bool **array) { for(int i = 0; i < x; ++i) memset(array[i], 0, sizeof(bool)*y); } int main(void) { int n, N, W, maxDiff, teamWeight, temp; int minWeight = MAX_WEIGHT, maxWeight = -1; cin >> N; while(N--) { cin >> n; W = 0; for(int i = 0; i < n; ++i) { cin >> weights[i]; if(weights[i] < minWeight) minWeight = weights[i]; if(weights[i] > maxWeight) maxWeight = weights[i]; W += weights[i]; } int maxW = maxWeight + (W>>1); int maxn = n>>1; int index = 0; /* table[j][i] = 1 if a team of j people can form i weight from K people, where k is implicit in loop table[j][i] = table[j-1][i-weight[j]] if i-weight[j] >=0 */ bool **table = create2D(maxn+1, maxW+1); //memset2D(maxn+1, maxW+1, table); //memset(table, 0, sizeof(table)); table[0][0] = true; /* for k people what can be formed?*/ for(int k = 0; k < n; ++k) { /* forming team of size j out of k people*/ for(int j = min(k, maxn) ; j >= 1; --j) { /* using j people out of k, can I make weight i?*/ for(int i = maxW; i >=minWeight ; --i) { if (table[j][i] == false) { /*do not consider k if more than allowable*/ index = i - weights[k]; if (index < 0) break; /*if without adding k, we can make the weight limit with less than one person then one can also make weight limit by adding k.*/ table[j][i] = table[j-1][index]; } /*outer if ends here*/ } /* ith loop */ } /* jth loop */ } /* kth loop */ maxDiff = MAX_WEIGHT_SUM ; teamWeight = 0; for(int i = 0; i <= maxW; ++i) { if (table[n/2][i]) { temp = abs(abs(W - i) - i); if (temp < maxDiff) { maxDiff = temp; teamWeight = i; } } } delete2D(n+1, maxW+1, table); teamWeight = min(teamWeight, W-teamWeight); cout << teamWeight << " " << W - teamWeight << endl; if(N) cout << endl; } return 0; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload