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
