There are enough pieces that you can get full credit for the assignment by doing only programming, by doing no programming, or by a combination of programming and pencil and paper work.

If you turn in any of the programming pieces,

• you are to define three Java classes -- Knapsack, Item, and Packing, as described below. The first two classes are to represent knapsacks and their items, while the last class is to represent solutions to knapsack problems. In particular, this last class is to be the return type of each of the four methods specified below.

• any of these four methods that you do not choose to turn in should be defined anyway, and should simply return null, so that the test method (the main method of the A2 class) will work. This class is provided on the class web site.

• the Item class should have a toString method that exhibits the benefit and weight of the item. It is to have a constructor that takes the integer weight and benefit of the item, in that order. This constructor should reject nonpositive values given for the weight (e.g., by converting the weight to 1 and the benefit to 0, or by throwing an exception. It should implement the Comparable interface, to facilitate sorting in nonincreasing order. It should be immutable.

• the Knapsack class is to have a constructor that takes an integer capacity and a List of items as arguments. It is to be immutable, but it is to have a second constructor that takes a capacity and a Knapsack as arguments, and returns a new Knapsack with the new capacity and the same items as the given Knapsack. It is to have a toString method that exhibits the capacity and the list of items. Both constructors should sort the list of items in nonincreasing order of profit density, so that printed Knapsack objects and list of items of Knapsack objects are easy to understand.

• the Packing class is to represent lists of amounts of items of a knapsack, where the items are ordered as in the knapsack's constructor. These amounts are to be of type double. The class is to be immutable. It is to have a toString method that exhibits the list of amounts, in order. It is to contain a representation of the underlying knapsack and a zero-argument public method getTotalBenefit, which returns the total benefit available from the given amounts of the items of the given knapsack. If you choose to do so for efficiency reasons, it is acceptable to give this class a constructor that takes the total benefit as an argument, without checking its consistency with the corresponding knapsack and list of amounts. If you do this, you should of course document this possible source of error.

• do be careful about safety issues, such as returning mutable instance fields.

The pieces of the assignment are as follows:

1. (20 points, programming or pencil and paper) Use the dynamic programming algorithm of the text to find the optimal solutions to the five zero-one knapsack instances with n=5, weight sequence (6, 5, 3, 4, 7), profit sequence (18, 14, 10, 13, 17), and capacities 9, 10, 11, 12, 13, and 25. If you use pencil and paper, you needn't use the algorithm for the capacity 25 case. Otherwise, you are to use a zero-argument method solveDynamically for the Knapsack class to do the job.

2. (20 points, programming only) Use the method of the previous piece to find the optimal solutions to the four zero-one knapsack instances with n=12, weight sequence (6, 5, 13, 14, 11, 10, 3, 4, 12, 9, 7, 8), profit sequence (22, 15, 51, 55, 42, 35, 11, 15, 42, 35, 31, 35), and capacities 80, 85, 90, and 95.

3. (20 points, programming or pencil and paper) Use exhaustive search of the power set of the set of items to find the optimal solutions to the first five zero-one knapsack instances of piece 1. If you take the programming option, you are to use a zero-argument method solveExhaustively for the Knapsack class to do the job. This method may use your solution (or my solution) to Assignment 1, it may proceed purely recursively, or it may use another technique. If you do not choose to program, express you answer in terms of a decision tree, where the levels of links in the tree correspond to making a yes/no decision on including each item, in the original order (not the sorted order).

4. (20 points, programming only) Use the method of the previous piece to find the optimal solutions to the four zero-one knapsack instances of piece 2.

5. (10 points, programming or pencil and paper) Use the greedy algorithm of the text to find the optimal solutions to the six instances of piece 1, interpreted as instances of the fractional knapsack problem. If you take the programming option, you are to use a zero-argument method solveFractional for the Knapsack class to do the job.

6. (10 points, programming or pencil and paper) Find approximate solutions to the six instances of piece 1, using the following greedy algorithm: consider the items in order of nonincreasing profit density, and include each item iff it fits into that portion of the knapsack not occupied by items already included. If you take the programming option, you are to use a zero-argument method solveGreedily for the Knapsack class to do the job.

7. (20 points, pencil and paper only) Show that there is no constant c such that the greedy algorithm of the previous piece returns a solution whose benefit is guaranteed to be within a factor of c of the optimal solution.

8. (20 points, pencil and paper only) Find an instance of the zero-one knapsack problem where no optimal solution includes either of the two items of greatest profit density, even though the sum of their weights is no larger than the knapsack capacity.