Python Dynamic Programing

Sample Input (Shopping.txt)

4 2 77 7 66 6 2 5 5 6 32 16 43 12 26 4 50 8 20 3 27 9 4 25 23 21 19 5 1 1 2 1 3 1 2 2 5 5 10 1 2 3 4 5 6 7 8 9 10 10 1 1 4 3 4 3 4 4 5 4 8 6 10 7 9 7 11 8 13 9 30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Sample Output (results.txt)

Test Case 1 Total Price 0 Member Items: 1: 2:

Test Case 2 Total Price 435 Member Items: 1: 3 4 5 6 2: 2 4 5 3: 3 4 6 4: 3 4 5

Test Case 3 Total Price 83 Member Items: 1: 3 2: 2 3 3: 1 2 3 4: 2 3 4 5: 1 2 3 4 6: 1 2 3 4 7: 2 3 5 8: 1 2 3 5 9: 2 3 4 5 10: 1 2 3 4 5

Test Case 4 Total Price 646 Member Items: 1: 1 2: 1 3: 2 4: 1 2 5: 1 5 6: 2 3 7: 7 8: 1 7 9: 10 10: 2 7 11: 1 2 7 12: 2 10 13: 2 3 7 14: 1 2 3 7 15: 7 9 16: 7 10 17: 1 7 10 18: 2 7 9 19: 2 7 10 20: 1 2 7 10 21: 2 3 7 9 22: 2 3 7 10 23: 1 2 3 7 10 24: 7 9 10 25: 2 6 7 10 26: 2 3 5 7 10 27: 2 7 9 10 28: 2 3 6 7 10 29: 1 2 3 6 7 10 30: 2 3 7 9 10

Problem 2: Shopping Spree: (15 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 a dynamic programming algorithm to determine the maximum total price of items for each family and the items that each family member should select. a) Give a verbal description and give pseudo-code for your algorithm. Try to create an algorithm that is efficient in both time and storage requirements. b) What is the theoretical running time of your algorithm for one test case given Nitems, a family of size F, and family members who can carry at most Mi pounds for 1sis F. c) Implement your algorithm by writing a program named "shopping (in C, C++ or Python) that compiles and runs on the OSU engineering servers. The program should satisfy the specifications below. Input: The input file named "shopping.txt" consists of T test cases T (1ST