Elysian Shadows

you are to write a program that does best possible balancing.
imagine this scenario, there is a tug of war, there are N people, and their weight are labeled as X.
you have to divide the two teams so that that their combined weights are as close as possible, and that one team may not have more that one extra competitor.

sample input

6 // number of people
6 // their weights follow
5
4
3
2
1

sample output

1 : 2
3 : 4
6 : 5
10 : 11

note: if there is one that has a smaller combined weight print it first.

i hope i explained it fairly decently, if you have any questions please feel free to ask.

thanks. i'll leave this one up till at least monday.
i havent done this one, but think it shouldn't be a problem.

ps: this has application in stratagy games, its used when the AI tries to figuer out what the minumum resources it can sacrifice to beat you and then weigh the other options to. but this concept applies to alot of game theory and game programming so encourage you to try.

My quick solution (hence the lack of generalization)

MarauderIIC wrote:My quick solution (hence the lack of generalization)

Click here to see the hidden message (It might contain spoilers)

Maximum difference is highest value, minimum difference is lowest value. So we want to leave the lowest value for last and add it to the most disadvantaged team.
However, if the # of values is even, then the two center values are closer than a center value and the lowest value. This works for consecutive #s where total is even and where total is odd, havent tested for nonconsecutive yet. And assuming I haven't pasted the wrong version, here it is:

Code: Select all

#include <deque>
#include <vector>
#include <algorithm>
#include <fstream>
#include <iostream>

using namespace std;

int main() {
	ifstream file("weights.txt");

	deque<int> weights;
	deque<int>::iterator second;
	vector<int> team1;
	vector<int> team2;
	int num;
	bool odd;

	file >> num;
	while (file) {
		weights.push_back(num);
		file >> num;
	}

	sort(weights.begin(), weights.end());
	if (weights.size() % 2 != 0)
		odd = true;
	else
		odd = false;

	cout << "Weights (sorted): ";
	for (deque<int>::iterator i = weights.begin(); i != weights.end(); ++i)
		cout << *i << " ";
	cout << endl;

	while (!weights.empty()) {
		team1.push_back(weights.back());	//get highest high
		weights.pop_back();
		if (weights.empty())
			break;
		team2.push_back(weights.back());	//get next highest high
		weights.pop_back();
		if (weights.empty())
			break;
		if (weights.size() == 1 || !odd) {
			team1.push_back(weights.front());
			weights.pop_front();
		} else {
			team1.push_back(*(weights.begin()+1));	//get next-to-lowest value
			weights.erase(weights.begin()+1);
		}
		if (weights.empty())
			break;
		if (weights.size() == 1 || !odd) {
			team2.push_back(weights.front());
			weights.pop_front();
		} else {
			team2.push_back(*(weights.begin()+1));	//get next-to-next-to-lowest
			weights.erase(weights.begin()+1);
		}
	}

	int total = 0;
	cout << "Total weights for team 1: ";
	for (vector<int>::iterator i = team1.begin();i != team1.end();++i) {
		cout << *i << " ";
		total += *i;
	}
	cout << " = " << total << endl;
	total = 0;
	cout << "# of players: " << team1.size() << endl;
	cout << "Total weights for team 2: ";
	for (vector<int>::iterator i = team2.begin();i != team2.end();++i) {
		cout << *i << " ";
		total += *i;
	}
	cout << " = " << total << endl;
	cout << "# of players: " << team2.size() << endl;
	system("pause");
	return 0;
}

run your solution to a bunch of inpute and tell us what the outputs are. i dont feel like building this solution now. hehe, but good work.

MarauderIIC wrote:My quick solution (hence the lack of generalization)

Click here to see the hidden message (It might contain spoilers)

Maximum difference is highest value, minimum difference is lowest value. So we want to leave the lowest value for last and add it to the most disadvantaged team.
However, if the # of values is even, then the two center values are closer than a center value and the lowest value. This works for consecutive #s where total is even and where total is odd, havent tested for nonconsecutive yet. And assuming I haven't pasted the wrong version, here it is:

Code: Select all

#include <deque>
#include <vector>
#include <algorithm>
#include <fstream>
#include <iostream>

using namespace std;

int main() {
	ifstream file("weights.txt");

	deque<int> weights;
	deque<int>::iterator second;
	vector<int> team1;
	vector<int> team2;
	int num;
	bool odd;

	file >> num;
	while (file) {
		weights.push_back(num);
		file >> num;
	}

	sort(weights.begin(), weights.end());
	if (weights.size() % 2 != 0)
		odd = true;
	else
		odd = false;

	cout << "Weights (sorted): ";
	for (deque<int>::iterator i = weights.begin(); i != weights.end(); ++i)
		cout << *i << " ";
	cout << endl;

	while (!weights.empty()) {
		team1.push_back(weights.back());	//get highest high
		weights.pop_back();
		if (weights.empty())
			break;
		team2.push_back(weights.back());	//get next highest high
		weights.pop_back();
		if (weights.empty())
			break;
		if (weights.size() == 1 || !odd) {
			team1.push_back(weights.front());
			weights.pop_front();
		} else {
			team1.push_back(*(weights.begin()+1));	//get next-to-lowest value
			weights.erase(weights.begin()+1);
		}
		if (weights.empty())
			break;
		if (weights.size() == 1 || !odd) {
			team2.push_back(weights.front());
			weights.pop_front();
		} else {
			team2.push_back(*(weights.begin()+1));	//get next-to-next-to-lowest
			weights.erase(weights.begin()+1);
		}
	}

	int total = 0;
	cout << "Total weights for team 1: ";
	for (vector<int>::iterator i = team1.begin();i != team1.end();++i) {
		cout << *i << " ";
		total += *i;
	}
	cout << " = " << total << endl;
	total = 0;
	cout << "# of players: " << team1.size() << endl;
	cout << "Total weights for team 2: ";
	for (vector<int>::iterator i = team2.begin();i != team2.end();++i) {
		cout << *i << " ";
		total += *i;
	}
	cout << " = " << total << endl;
	cout << "# of players: " << team2.size() << endl;
	system("pause");
	return 0;
}

i didn't think it was gonna work

weights.txt
1
2
11
32
22
43
7
8
9

output

Weights (sorted): 1 2 7 8 9 11 22 32 43
Total weights for team 1: 43 2 22 8 1 = 76
# of players: 5
Total weights for team 2: 32 7 11 9 = 59
# of players: 4
Press any key to continue . . .

thas the wrong out put.

this is the right output:

Weights (sorted): 1 2 7 8 9 11 22 32 43
Total weights for team 1: 1 2 9 11 43 = 66
# of players: 5
Total weights for team 2: 7 8 22 32 = 69
# of players: 4

BIG HINT : I feel i should post this because this is quite integral to the challenge. Just one word. Permutation

i had never done this one, so i thought i could participate as well. dont look if you dont wanna know the answer.
my code is very slopy in the beginning, but the main mechanic of the program u feel is pretty well done. might be a bit hard to understand, but that just because this problem is not that easy. any comments will be appreciated.

yea so it works. it just prints out a selection of one team, i didnt mess to make it like i said, but it does work. it pretty sweet. the first bit is very ugly code, but the block i indicated is just gorgeous.

Done! Works beautifully
Due to the fact that it's illegal for the challenge maker to join.. I ARE VICTORIOUS! xD


And btw, that "Big Hint", "Permutation" thing.. what was that about..?! :S
Not really a big hint.. Especially for those like me, who don't go to school :P

cypher1554R wrote:Done! Works beautifully

Code: Select all

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <math.h>
#include <vector>
#include <conio.h>

bool T1done = false;

std::vector<int> T1, T2a, T2b;

std::string IntToStr(int iNum)
{
	std::ostringstream oss;
	oss << iNum;
	std::string s(oss.str());
	return s;
}

int StrToInt(std::string str)
{
	int i;
	std::istringstream iss(str);
	iss >> i;
	return i;
}

void sortHiToLo(std::vector<int> &ivec);
int VISum(std::vector<int> &veci);
void balance(std::vector<int> &mainv, std::vector<int> &veciA, std::vector<int> &veciB);

int main ()
{
	std::cout << "Add members, press 'enter' for each addition.\n"
		<< "press 'tab' after you're done\n\n";
	system("PAUSE");
	std::string thug;

	//teamA
	while(true)
	{
		system("cls");
		std::cout << "So far (" << T1.size() << "): ";
		for(int i = 0; i < (int)T1.size(); i++)
			std::cout << T1[i] << " : ";
		char cch;
		thug.clear();
		std::cout << "\n\nWeight " << T1.size() + 1 << ": ";
		while(true)
		{
			cch = getch();
			if(cch >= 48 && cch <= 57) {
				thug.push_back(cch);
				std::cout << cch;
			}
			else if(cch == 13)
				break;
			else if(cch == 9) {
				T1done = true;
				break;
			} else {
				std::cout << "input out of range!!!one\n";
				system("PAUSE");
				break;
			}
		}
		if(T1done && T1.size() == 0) {
			std::cout << "There has to be at least one in each team!\n";
			continue;
		}
		if(T1done && T1.size() > 0) {
			break;
		}
		int len = (int)thug.size();
		if(len == 0) {
			continue;
		}
		T1.push_back(StrToInt(thug));
	}
	std::cout << "\nSorting: ";
	sortHiToLo(T1);
	for(int i = 0; i < T1.size(); i++)
		std::cout << T1[i] << " : ";
	balance(T1, T2a, T2b);
	std::cout << "\n\nTeam A: ";
	for(int i = 0; i < T2a.size(); i++)
		std::cout << T2a[i] << " : ";
	std::cout << ">> " << VISum(T2a);
	std::cout << "\nTeam B: ";
	for(int i = 0; i < T2b.size(); i++)
		std::cout << T2b[i] << " : ";
	std::cout << ">> " << VISum(T2b) << "\n\n";

	system("PAUSE");
	return 0;
}

int getHighest(std::vector<int> &ivec)
{
	int hi = ivec[0];
	int j = 0;
	for(int i = 1; i < ivec.size(); i++)
		if(ivec[i] > hi)
		{
			hi = ivec[i];
			j = i;
		}
	return j;
}

void sortHiToLo(std::vector<int> &ivec)
{
	std::vector<int> temp;
	int len = ivec.size();
	for(int i = 0; i < len; i++)
	{
		int hi = getHighest(ivec);
		temp.push_back(ivec[hi]);
		ivec.erase(ivec.begin() + hi);
	}
	for(int i = 0; i < temp.size(); i++)
		ivec.push_back(temp[i]);
}

int VISum(std::vector<int> &veci)
{
	int temp = 0;
	for(int i = 0; i < veci.size(); i++)
		temp += veci[i];
	return temp;
}

void balance(std::vector<int> &mainv, std::vector<int> &veciA, std::vector<int> &veciB)
{
	for(int i = 0; i < mainv.size(); i++)
	{
		int sumA = VISum(veciA);
		int sumB = VISum(veciB);
		if(sumA > sumB)
			veciB.push_back(mainv[i]);
		else
			veciA.push_back(mainv[i]);
	}
}

Due to the fact that it's illegal for the challenge maker to join.. I ARE VICTORIOUS! xD


And btw, that "Big Hint", "Permutation" thing.. what was that about..?! :S
Not really a big hint.. Especially for those like me, who don't go to school :P

umm. i dont think its working 100%

avansc wrote:umm. i dont think its working 100%

Hah! That's too bad, cause it is.

cypher1554R wrote:

avansc wrote:umm. i dont think its working 100%

Hah! That's too bad, cause it is.

well i get this output from your program.

So far (9): 1 : 2 : 7 : 8 : 9 : 11 : 22 : 32 : 43 :

Weight 10:
Sorting: 43 : 32 : 22 : 11 : 9 : 8 : 7 : 2 : 1 :

Team A: 43 : 11 : 9 : 2 : 1 : >> 66
Team B: 32 : 22 : 8 : 7 : >> 69

Press any key to continue . . .

that is not the best balance. you can get a 68:67 ratio.

with combination 43 : 22 : 2 : 1 = 68

Oh, now you're just splitting hairs >:[


xP

Mine worked on inputs 9 8 7 6 5 4 3 2 1 and 8 7 6 5 4 3 2 1
Mine doesn't conform to your file format standard either, though. Notice I said it wasn't tested on nonconsecutives, I wrote it in 30 minutes between classes ;)

cypher1554R wrote:Oh, now you're just splitting hairs >:[


xP

well your program still doesent work

MarauderIIC wrote:Mine worked on inputs 9 8 7 6 5 4 3 2 1 and 8 7 6 5 4 3 2 1
Mine doesn't conform to your file format standard either, though. Notice I said it wasn't tested on nonconsecutives, I wrote it in 30 minutes between classes

yeah, i dont really care about file format, you can do that any way you want.
but yeah your program also does not work.

avansc wrote:

cypher1554R wrote:Done! Works beautifully

Code: Select all

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <math.h>
#include <vector>
#include <conio.h>

bool T1done = false;

std::vector<int> T1, T2a, T2b;

std::string IntToStr(int iNum)
{
	std::ostringstream oss;
	oss << iNum;
	std::string s(oss.str());
	return s;
}

int StrToInt(std::string str)
{
	int i;
	std::istringstream iss(str);
	iss >> i;
	return i;
}

void sortHiToLo(std::vector<int> &ivec);
int VISum(std::vector<int> &veci);
void balance(std::vector<int> &mainv, std::vector<int> &veciA, std::vector<int> &veciB);

int main ()
{
	std::cout << "Add members, press 'enter' for each addition.\n"
		<< "press 'tab' after you're done\n\n";
	system("PAUSE");
	std::string thug;

	//teamA
	while(true)
	{
		system("cls");
		std::cout << "So far (" << T1.size() << "): ";
		for(int i = 0; i < (int)T1.size(); i++)
			std::cout << T1[i] << " : ";
		char cch;
		thug.clear();
		std::cout << "\n\nWeight " << T1.size() + 1 << ": ";
		while(true)
		{
			cch = getch();
			if(cch >= 48 && cch <= 57) {
				thug.push_back(cch);
				std::cout << cch;
			}
			else if(cch == 13)
				break;
			else if(cch == 9) {
				T1done = true;
				break;
			} else {
				std::cout << "input out of range!!!one\n";
				system("PAUSE");
				break;
			}
		}
		if(T1done && T1.size() == 0) {
			std::cout << "There has to be at least one in each team!\n";
			continue;
		}
		if(T1done && T1.size() > 0) {
			break;
		}
		int len = (int)thug.size();
		if(len == 0) {
			continue;
		}
		T1.push_back(StrToInt(thug));
	}
	std::cout << "\nSorting: ";
	sortHiToLo(T1);
	for(int i = 0; i < T1.size(); i++)
		std::cout << T1[i] << " : ";
	balance(T1, T2a, T2b);
	std::cout << "\n\nTeam A: ";
	for(int i = 0; i < T2a.size(); i++)
		std::cout << T2a[i] << " : ";
	std::cout << ">> " << VISum(T2a);
	std::cout << "\nTeam B: ";
	for(int i = 0; i < T2b.size(); i++)
		std::cout << T2b[i] << " : ";
	std::cout << ">> " << VISum(T2b) << "\n\n";

	system("PAUSE");
	return 0;
}

int getHighest(std::vector<int> &ivec)
{
	int hi = ivec[0];
	int j = 0;
	for(int i = 1; i < ivec.size(); i++)
		if(ivec[i] > hi)
		{
			hi = ivec[i];
			j = i;
		}
	return j;
}

void sortHiToLo(std::vector<int> &ivec)
{
	std::vector<int> temp;
	int len = ivec.size();
	for(int i = 0; i < len; i++)
	{
		int hi = getHighest(ivec);
		temp.push_back(ivec[hi]);
		ivec.erase(ivec.begin() + hi);
	}
	for(int i = 0; i < temp.size(); i++)
		ivec.push_back(temp[i]);
}

int VISum(std::vector<int> &veci)
{
	int temp = 0;
	for(int i = 0; i < veci.size(); i++)
		temp += veci[i];
	return temp;
}

void balance(std::vector<int> &mainv, std::vector<int> &veciA, std::vector<int> &veciB)
{
	for(int i = 0; i < mainv.size(); i++)
	{
		int sumA = VISum(veciA);
		int sumB = VISum(veciB);
		if(sumA > sumB)
			veciB.push_back(mainv[i]);
		else
			veciA.push_back(mainv[i]);
	}
}

Due to the fact that it's illegal for the challenge maker to join.. I ARE VICTORIOUS! xD


And btw, that "Big Hint", "Permutation" thing.. what was that about..?! :S
Not really a big hint.. Especially for those like me, who don't go to school :P

umm. i dont think its working 100%

you are not victorious, and the hint is a big hint, and you do not have to go to school to know what a permutation is.