Recursion - Data Structures and Abstractions with Java - page 186

5.

Imagine an array of n items from which you can choose. You will place the items you choose into a knapsack of
size k . Each item has a size and a value. Of course, you cannot take more items than you have space for in the
knapsack. Your goal is to maximize the total value of the items you take.
a. Design a recursive algorithm maxKnapsack to solve this knapsack problem. The parameters to the algo-
rithm are the knapsack, the array of items, and the position within the array of the next item to consider.
The algorithm chooses the items for the knapsack and returns a knapsack containing the chosen items.
A knapsack can report its size, its contents, the value of its contents, and the size of its contents.
Hint : If any items in the array have not yet been considered, retrieve the next item in the array. You can
either ignore the item or, if it fits, put it in the knapsack. To decide, make a recursive call for each of these
two cases. Compare the knapsacks returned by these calls to see which one has the most valuable contents.
Then return that knapsack.
b. Write the classes Knapsack and KnapsackItem . Then write a program that defines the method maxKnapsack .
The program should read the size of the knapsack and then the size, value, and name of each available item.
Here is some sample input data for a knapsack of size 10:

Size Value Name
1 50000 rare coin
2 7000 small gold coin
4 10000 packet of stamps
4 11000 pearl necklace
5 12000 silver bar
10 60000 painting
After displaying the items, call maxKnapsack . Then display the chosen items, their values, and their total value.

6.

Suppose that you are scheduling a room. You are given a group of activities each of which has a start time and
stop time. Two activities are compatible if they do not overlap. For example, in the following activities, activity
A is compatible with activities B and D, but not activity C:

Activity Start Time Stop Time

A 1 2

B 2 5

C 1 3

D 5 6

Your goal is to schedule compatible activities that result in a maximum usage of the room.
a. Design a recursive algorithm to solve this room-scheduling problem. The method whose signature is

maxRoomUse( int startTime, int stopTime, Activity[] activities)

returns a pair consisting of the maximum usage in hours and an array of activities scheduled. Note that
startTime is the first time that an activity can be scheduled, stopTime is the final time, and activities is
an array of possible activities.
b. Write the class Activity and a class Schedule that represents the pair that maxRoomUse returns. Then write a
program that defines the method maxRoomUse . The program should read the start time and stop time for the
room followed by the start and stop times for each activity (one activity per line). After displaying the given
activities, display the maximum usage in hours of the room along with a list of the scheduled activities.