Question

Python Knapsack Problem:

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.

***In python:***

Implement your algorithm by writing a program named “shopping.py”. The program should satisfy 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 ≤ 30) 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 “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:

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:

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

Answer 1

CREATE ALGORITHM THAT IS EFFICIENT IN BOTH TIME AND STORAGE REQUIREMENTS.

Algorithm :-

Let the total Item types be N i.e I ₁, I ₂, I ₃... I_n.

Let the total Family members be F i.e P ₁, P ₂, P ₃.....P_f.

Now, each person can carry only 1 item of each type such that the his/her carrying capacity is not overwhelmed.

Let OPT(N,F) be the maximum price of items that a family of size F can carry  from a set of N item types subject to the condition each member carries only 1 item of each type and total weight of items he/she is carrying is less than or equal to his/her carrying weight.

Let Best(P_i,N) be optimal price of items that the Family Member P_i is carrying from
the set of N item types subject to the condition that he/she can carry only 1 item of each type
and total weight of items P_i is carrying <= Pi's total carrying capacity

We see that OPT(N,F) = OPT(N,F-1) + Best(Pf,N)

   Let's denote Best(P_i,N) = F(N,W_i) i.e F(N,W_i) represents the optimal price of the items selected from N items such that the total weight of items selected <= W_i and W_i >= 0
It's easy to see from recursion that :-  

F(N,W_i) = max{ F(N-1, W_i - weight(Item(N)) ) + Price(Item(n)) , F(N-1, W_i) }

(b) THE THEORETICAL RUNNING TIME OF ALGORITHM :-

To run Knapsack algorithm for each family member to the time complexity of each Best(P_i,N) = O(N*M_i) where M_i  is the carrying capacity of the family member P_i. Since there are a total of F family members, total time complexity 9=

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.

C CODE :-

1. #include<stdio.h>
2. #include<stdlib.h>
3. int knapsack(int memberCapacity,
4. int items[101][2],
5. int n,
6. int selectedItems[101],
7. int* perMemberItems){
8. int i,j,k;
9. int f[101][201];
10. for(i=0;i<201;i++){
11. f[0][i] = 0;
12. }
13. for(i=0;i<101;i++){
14. f[i][0] = 0;
15. }
16. for(i=1;i<=n;i++){
17. for(j=1;j<=memberCapacity;j++){
18. if(j - items[i][1] >= 0 ){
19. int tempCost = f[i-1][j-items[i][1]] + items[i][0];
20. if(tempCost > f[i-1][j]){
21. f[i][j] = tempCost;
22. }else{
23. f[i][j] = f[i-1][j];
24. }
25. }else{
26. f[i][j] = f[i-1][j];
27. }
28. }
29. }
30. int weight = memberCapacity;
31. k = 0;
32. for(i=n;i>0;i--){
33. if(weight < 0 ){
34. break;
35. }
36. if(weight - items[i][1] >= 0 ){
37. if(f[i-1][weight-items[i][1]] + items[i][0] > f[i-1][weight] ){
38. selectedItems[k++] = i;
39. weight = weight - items[i][1];
40. }
41. }
42. }
43. *perMemberItems = k;
44. return(f[n][memberCapacity]);
45. }
46. int main(){
47. int i,j,k,n,t,f;
48. FILE *fin = fopen("shopping.txt","r");
49. FILE *fout = fopen("results.txt","w");
50. fscanf(fin,"%d",&t);
51. int items[101][2];
52. int family[31];
53. int selectedItems[31][101];
54. int perMemberItems[31];
55. k = 1;
56. while(t > 0){
57. fscanf(fin,"%d",&n);
58. for(i=1;i<=n;i++){
59. fscanf(fin,"%d%d",&items[i][0],&items[i][1]);
60. }
61. fscanf(fin,"%d",&f);
62. for(i=0;i<f;i++){
63. fscanf(fin,"%d",&family[i]);
64. }
65. int totalCost = 0;
66. fprintf(fout,"Test Case %d ",k);
67. for( i=0;i<f;i++){
68. totalCost += knapsack(family[i],items,n,selectedItems[i],&perMemberItems[i]);
69. }
70. fprintf(fout,"Total Price %d ",totalCost);
71. fprintf(fout,"Member Items ");
72. for(i=0;i<f;i++){
73. fprintf(fout,"%d:",i+1);
74. for(j=perMemberItems[i]-1;j>=0;j--){
75. fprintf(fout," %d",selectedItems[i][j]);
76. }
77. fprintf(fout," ");
78. }
79. t--;
80. k++;
81. }
82. fclose(fin);
83. fclose(fout);
84. return(0);
85. }

Output: