Project 2: Balanced Teams Solution

Description

The purpose of this assignment is to give you some practice designing and implementing an algorithm based on the exhaustive search algorithm design strategy.

The Problem Oroku is a senior manager at a medium-sized corporation, in charge of assigning workers to various projects. He knows that some of his employees are much better workers than others; in fact, he is such a good manager that he has assigned a numerical score to each employee that measures their overall ability.

In one particular episode of the company’s life, there are two projects to complete, both equally important. Thus, Oroku wants to divide his team into two equally-competent groups. That is, he needs to choose the two teams carefully to ensure that the total skill level between the two teams is equal, while still ensuring that every worker is assigned to one of the two teams.

For example, suppose these workers are available.

Name Ability

Baxter 13

Lonae 37

Mephos 25

Mozar 33

Savanti 32

In that case, if Oroku forms these two teams, the total ability of each team will be equal (namely, 70).

Team A

Team B

Baxter

Lonae

Mephos

Mozar

Savanti

In this project, you will create a decision support system to help Oroku allocate his employees to these kinds of equally-balanced pairs of project teams.

Your Task Your job for this project is to write a program that reads the names and skill levels of the available employees and organizes them, if possible, into two teams with equal total skill level. Specifically, you should write a C++ program that does precisely these things:

1. Read a positive integer n from standard input. This represents the number of employees.

2. Read n lines, each describing one employee. Each line will have name and a skill level, separated by a space. Each name will be a sequence of letters (i.e. with no spaces). Each skill level will be an integer (which might be negative, positive, or zero).

3. Determine, using some form of exhaustive search, how those employees can be split into two teams with equal total skill level. Because every solution has a ‘twin’ in which the names of the two teams are swapped, you should find only solutions in which the first employee is assigned to Team A.

4. Show the solutions.

If there is a solution, show it like this, listing the names of the employees assigned to each team.

Team A:

name₁

.

.

.

name_m

Team B:

name₁

.

.

.

name_{n m}

The names within each team should be listed in the same order that they appear in the input.

If there are multiple solutions, show all of them, separated by blank lines. If there are no solutions, output a line containing ‘No solution.’.

See the samples below for specific illustrations of the output format.

5. Return to Step 1 above to read and process another instance. When there are multiple instances, separate the output for each one with a line containing ‘————’. Terminate when standard input reaches end-of-file.

Here are a few example inputs with the correct output for each one.

Sample Input 1 Sample Output 1

5 Team A:

Baxter 13 Baxter

Lonae 37 Mephos

Mephos 25 Savanti

Mozar 33 Team B:

Savanti 32 Lonae

Mozar

Sample Input 2	Sample Output 2
4	No solution.
Friday 13	————
Sarah 12	Team A:
Wednesday 9	Donkey
Thursday 14	Daniel
4	Team B:
Donkey 3	Cornflake
Daniel 6	Bob
Cornflake 3
Bob 6	Team A:
	Donkey
	Bob
	Team B:
	Daniel
	Cornflake

Sample Input 3 Sample Output 3

1 No solution.

Tim 99

An additional much longer sample input, along with its correct corresponding output, is available on the course website.

Notes A few possibly helpful comments:

For calibration purposes, my solution has 50 lines of code. Yours may be longer, but if you find yourself writing huge amounts of code, something has probably gone wrong.

Keep in mind that you are expected to submit your own original work for this problem. Accessing reference material for C++ in general is fine and encouraged. However, you are strongly discouraged from conducting web searches for code specific to the corporate team allocation problem.

What to Submit You should submit, using the department’s dropbox website, a single C++ source file con-taining all of the code for your program. We will compile this program using this command line:

g++ -Wall -std=c++11 yourfile.cpp

csce350 Project 2: Balanced Teams 3 of 3