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++
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
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