Lab 1: A Task for Children or Computers

OBJECTIVES

To continue learning Java and to design your own algorithm.

RELATED EXPERIENCE

After several years of elementary school teaching, I learned how to divide goodies between two children so that both think they are getting a fair deal: choose one of the children to divide the goodies into two parts, and then let the other child pick which part he/she wants. Note that the goal of the child who divides is to get as even of a split as possible.

SCENARIO

You and a greedy classmate win a large sack of gems. You take the gems to a reputable gem appraiser who determines the value of each gem. One of you wants to sell the gems and split the profit down the middle, but the other wants to hold onto the gems. You ask your data structures teacher for advice, and she suggests that the two of you divide up the rocks (no gem can be split in two, tho) in the following manner: it is your job to divide the gems into two piles; your classmate gets to choose which pile he/she wants.

ASSIGNMENT

Write a Java program that takes as input a list of gem values and divides the gems into two piles such that the sum of the values of the rocks in the two piles is close to equal. The values can be any positive integer that does not exceed 50,000. You may assume that the sum of the values does not exceed the maximum integer value for 32 bit integers.

  1. Give a menu allowing for two different kinds of input entry:
    1. Read the name of a file in the program, then read the gem values from that file: the first entry in the file is the number of gems, followed by that number of gem values. The values are delimited by whitespace.
    2. Ask the user how many gems are in the bag, and then choose that many random numbers (random numbers could be from 1..50,000).
  2. Have the program figure out a fair way to divide the gems.
  3. Produce the following output:
    1. The original list of gem values
    2. The gem values in the first group: and the sum of this group
    3. The gem values in the second group: and the sum of this group

    EXAMPLE 1

    Gem Values:
  26004   39663   29502   40739   14724   15188   48659   47360
   3106     777    6038    5010   33108     213   26954   43668

Pile #1.  
  48659  40739  39663  29502  26004   5010    777
Sum: 190354

Pile #2.  
  47360  43668  33108  26954  15188  14724   6038   3106    213
Sum: 190359

    EXAMPLE 2

    Gem Values:
   25342   12858   14827   15960   35321   18784   24278   23101
    9727   44395   25120   41247    9868   27622    1796   16221
   29060   11148   39333   45273   10494    3486   44636   19997
   15941    5572   41958   22909   20382   45803   37723   12075
   25012   18901   28034   26685   37684   18664   49785   47410
   13058   24905   38657   39278    2526    6804    5498   47937
   34304   11183

Pile #1.  
  49785  47937  47410  45803  45273  44636  44395  41958  41247  39333
  39278  38657  37723  27622  11148   6804   3486   1796
Sum: 614291

Pile #2.  
  37684  35321  34304  29060  28034  26685  25342  25120  25012  24905
  24278  23101  22909  20382  19997  18901  18784  18664  16221  15960
  15941  14827  13058  12858  12075  11183  10494   9868   9727   5572
   5498   2526
Sum: 614291

    GRADING

    Your lab will be graded on the following, with approximate point values shown:

    DUE DATE

    The due date is January 20th at midnight.