Gifting Problem

Problem statement:

Suppose you are in charge of a non-profit organization that receives donated gifts and distributes them to

needy children. You are given a list of children with their ages (0 to 16 years old).

For each gift, you are given the following information:

Retail price

Size of gift (cubic feet)

Range of suitable ages

Let: P = sum of retail prices of the gifts

N = total number of children

ei = | P/N – sum of retail prices for gifts given to child i |

You must minimize Σ ei for the N children, subject to the following constraints:

1. Each gift must be given to exactly one child.

2. No child may be given a gift that is not intended for their age.

3. Each child must receive at least one large and one medium gift, where 1 ft3 <= medium gift <= 2 ft3, and

2 ft3 < large gift.

4. The number of gifts received by each child can be no less than the average – 1 and no more than the

average + 1.

Important:

The sum of the e_i values MUST be the absolute lowest value that is possible for the given input file.

Command line: ./gifting inputFileName outputFileName

Rubric:

Compiles, good programming style, processes command line arguments 15 pts.

Produces correctly formatted output file with all children and gifts included 10 pts.

Produces optimal solution 70 pts.

Compute time/space efficiency, creativity 5 pts. + extra credit possible

Notes:

1. Extra credit could possibly be large

2. Programming style based on Department Standards (see Programming Standards file on Canvas)

3. A signed Academic Integrity statement must be submitted to receive credit

Programs that do not compile and produce an executable on Clark will not be graded

Programs MUST be written in C/C++

Input format:

Plain text tab-delimited file. See example on next page. Child1 age 8

Child2 age 6

Child3 age 4

Gifts Price Size Ages

G1 12 1.3 7-14

G2 15 2.5 any

G3 8 1.5 0-5

G4 22 2.8 6-16

G5 10 1.5 any

G6 11 2.1 any

Output format:

The output should be a plain text tab-delimited file. It must begin with ‘Sum_e_i x’, where x is the sum of the ei

values. This should be followed by N rows, one for each child (in order), with their assigned gifts and ei value

as follows:

Sum_e_i 12.0

Child1 G1 G6 3

Child2 G5 G4 6

Child3 G3 G2 3