# Question: preferred language is python but c is good as well...

###### Question details

Preferred language is Python, but C++ is good as well. It must be able to read a txt file of inputs and then post its results to another txt file. Be sure to read the specifications of the input file (feel free to ask if you need clarification). This is a variant of the knapsack problem, where you must be able to get the maximum price of items that the entire family can carry while also listing the items that each individual family member should select. Use dynamic programming. Please help with all parts and explain your reasoning, especially with understanding how the running time is found (part b). Thank you.

a) 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 N items, a family of size F, and family members who can carry at most Mi pounds for 1 <= i <= F.

c) Implement your algorithm by writing a program named “shopping”. The program should satisfy the specifications below:

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

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

2. 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

3. 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.

4. The next line contains one integer (1 <= F <= 30) which is the number of people in that family.

5. The next F lines contains the maximum weight (1 <= M <= 200) that can be carried by the i th person in the family (1 <= i <= F).

Output: Written to a file named “results.txt”. 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 .txt File:

2

3

72 17

44 23

31 24

1

26

6

64 26

85 22

52 4

99 18

39 13

54 9

4

23

20

20

36

Sample Output txt File:

Test Case 1

Total Price 72

Member Items

1: 1

Test Case 2

Total Price 568

Member Items

1: 3 4

2: 3 6

3: 3 6

4: 3 4 6