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.
Implement your algorithm by writing a program named shopping that 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 the object and the second integer (1 <= W <= 100) corresponds to the weight of the 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 i^th person in the family (1 <= i <= F).

Output:
Written to a filed 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 family member, numbered 1 <= i <= F, list the item numbers 1 <= N <= 100 that they should select.
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

see explaination

Explanation:

/*shopping.cpp*/

#include<iostream>

#include<fstream>

#include<algorithm>

using namespace std;

int knapsackDP(int[], int[], int, int);

int max(int, int);

int main()

{

int T; // no. of test cases

int N; // no. of items

int P[100]; // prices of items

int W[100]; // weights of items

int F; // no. of people in the family

int M = 0; // Maximum weight that can be carried

ifstream inFile;

ofstream outFile;

// open input file

inFile.open("shopping.txt");

// check whether the input file is opend or not

if (!inFile.is_open())

{

cout << "can't open the file" << endl;

return 1;

}

// open the output file

outFile.open("shopping.out");

// check whehter the output file is opened or not

if (!outFile.is_open())

{

cout << "can't open the file" << endl;

return 1;

}

// read the number of test cases from the input file

inFile >> T;

// process T number of test cases

for (int k = 0; k<T; k++)

{

// read the number of items from the input file

inFile >> N;

// read the price and weight of each item

// into respective arrays

for (int i = 0; i<N; i++)

{

inFile >> P[i];

inFile >> W[i];

}

int maxTPrice = 0;

// read number of family members

inFile >> F;

// find maximum price of items that can be carried by

// each family member and keep track the total of the

// maximum prices

for (int j = 0; j<F; j++)

{

// read the maximum weight that can be carried by a

// current family member

inFile >> M;

// find maximum price of items that can be carried by

// current family member and add it to maxPrice

maxTPrice = maxTPrice + knapsackDP(W, P, N, M);

}

// Write the maximum total price to output file

outFile << maxTPrice << endl;

// Write the maximum total price to console

cout << maxTPrice << endl;

}

// close the files

inFile.close();

outFile.close();

return 0;

}

// returns the maximum price of items that can be carried

// by a person, who can carry maximum weight M

int knapsackDP(int W[], int P[], int N, int M)

{

int K[N + 1][M + 1];

// Build table K[][]

for (int i = 0; i <= N; i++)

{

for (int w = 0; w <= M; w++)

{

if (i == 0 || w == 0)

{

K[i][w] = 0;

}

else if (W[i - 1] <= w)

{

K[i][w] = max(P[i - 1] + K[i - 1][w - W[i - 1]], K[i - 1][w]);

}

else

{

K[i][w] = K[i - 1][w];

}

}

}

// stores the result of Knapsack

int res = K[N][M];

int w = M;

for (int i = N; i > 0 && res > 0; i--)

{

if (res == K[i - 1][w])

continue;

else

{

// Since this weight is included its

// value is deducted

res = res - P[i - 1];

w = w - W[i - 1];

}

}

// K[N][M] represents the maximum price of items that can be carried by

// the family member

return K[N][M];

}

// returns maximum of two parameters that are received

int max(int a, int b)

{

if (a > b)

return a;

else

return b;

}