Homework Assignment 3 Solution

Problem 1. Canoe Rental Problem: (10 points) : There are n trading posts numbered 1 to n as you travel downstream. At any trading post i you can rent a canoe to be returned at any of the downstream trading posts j, where j i. You are given an array R[i, j] defining the costs of a canoe which is picked up at post i and dropped off at post j, for 1 ≤ i ≤ j ≤ n. Assume that R[i,i] = 0 and that you can’t take a canoe upriver. Your problem is to determine a sequence of rentals which start at post 1 and end at post n, and that has the minimum total cost.




Describe verbally and give pseudo code for a DP algorithm called CanoeCost to compute the cost of the cheapest sequence of canoe rentals from trading post 1 to n. Give the recursive formula you used to fill in the table or array.



Using your results from part a) how can you determine the sequence of trading posts from which canoes were rented? Give a verbal description and pseudo code for an algorithm called PrintSequence to retrieve the sequence.



What is the running time of your algorithms?



Problem 2: Shopping Spree: (20 points) Acme Super Store is having a contest to give away shopping sprees to lucky families. If a family wins a shopping spree each person in the family can take any items in the store that he or she can carry out, however each person can only take one of each type of item. For example, one family member can take one television, one watch and one toaster, while another family member can take one television, one camera and one pair of shoes. Each item has a price (in dollars) and a weight (in pounds) and each person in the family has a limit in the total weight they can carry. Two people cannot work together to carry an item. Your job is to help the families select items for each person to carry to maximize the total price of all items the family takes. Write an algorithm to determine the maximum total price of items for each family and the items that each family member should select.




Submit to Canvas




A verbal description and give pseudo-code for your algorithm. Try to create an algorithm that is efficient in both time and storage requirements.



What is the theoretical running time of your algorithm for one test case given N items, a family of size F, and family members who can carry at most Mi pounds for 1 ≤ i ≤ F.



Implement your algorithm by writing a program named “shopping” that compiles/runs on the OSU engineering servers and follows the specifications below.



Input: The input file named “shopping.txt” consists of T test cases




T (1 ≤ T ≤ 100) is given on the first line of the input file.




Each test case begins with a line containing a single integer number N that indicates the number




of items (1 ≤ N ≤ 100) in that test case




Followed by N lines, each containing two integers: P and W. The first integer (1 ≤ P ≤ 5000) corresponds to the price of object and the second integer (1 ≤ W ≤ 100) corresponds to the




weight of object.

The next line contains one integer (1 ≤ F ≤ 100) which is the number of people in that family.







The next F lines contains the maximum weight (1 ≤ M ≤ 200) that can be carried by the ith person in the family (1 ≤ i ≤ F).




Output: Written to a file named “shopping.out”. For each test case your program should output the maximum total price of all goods that the family can carry out during their shopping spree and for each the family member, numbered 1 ≤ i ≤ F, list the item numbers 1 ≤ N ≤ 100 that they should select.




Sample Input

2

3

17
23
24



 
 
 
26
22
4
18
13
9



 
 
 
 
 



Sample Output:

Test Case 1

Total Price 72

Member Items




1 Test Case 2 Total Price 568 Member Items



3 4
3 6
3 6
3 4 6






Submit to TEACH a zipped file containing your code files and README file.




Note: You will not be collecting experimental running rimes.