Problem 3: (15 points) Shopping Spree Acme Super Store is having a contest to gi

Question

Problem 3: (15 points) Shopping Spree
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 a single object. 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. What is the maximum price of items the family can select?
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 ? 1000) 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 ? 100) 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 calculate one integer which is the maximum total price of all goods that the family in can carry out during their shopping spree.
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
26

Sample Output
72
514
Submit to Canvas
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.cpp” that compiles with g++ on the OSU
engineering servers. Submit your code to TEACH in a zipped file.
Note: You will not be collecting experimental running rimes.
Extra Credit: Determine the exact items each family member should take. Output the family member number 1
? i ? F and on the same line the item numbers 1 ? N ? 100 that they should select. Describe your algorithm and
data structures in detail and give the running time. Name your extra credit program “extra.cpp” and write the
results to a file named “extra.out”. Submit your code to TEACH in a zip file with the solution to problem 3.
Sample Input:
1
3
10 5
20 10
40 15
2
12
28
Sample Output:
Total Price 80
Member Items
1: 2
2: 2 3

Explanation / Answer

/*
************************************************************************************
Explaination:
For each member of the family, solve for 0-1 knapsack using dynamic programming
For the extra credit part, apply backtracking on the DP table to know which item was taken by each member
************************************************************************************
*/

/*
************************************************************************************
shopping.cpp
************************************************************************************
*/

#include <iostream>
#include <fstream>
#include <string>
#include <stdio.h>

using namespace std;

int solveKnapsack(int P[],int W[],int M,int N) // solves an 0-1 knapsack problem
{
int K[N + 1][M + 1]; // K[i][w] stores the maximum value obtained considering items from 0 to i, with a maximum weight limit of w
for (int i = 0; i <= N; i++) // iterate over all the items
{
for (int w = 0; w <= M; w++) // iterate over the range of weights
{
if(i==0||w==0) // if number of items or maximum weight allowed is zero
K[i][w] = 0; // set K[i][w] to 0
else if(W[i-1]<=w) // if weight of current item is lesser than the maximum allowed weight
K[i][w] = max(P[i - 1] + K[i - 1][w - W[i - 1]], K[i - 1][w]); // choose the maximum value, based on whether you include the current item or not
else
K[i][w] = K[i - 1][w]; // current item cannot be included
}
}
return K[N][M]; // return K[N][M] as the solution
}

int solve(int P[],int W[],int M[],int N,int F)
{
int total_price = 0; // accumulates the total price
for (int i = 0; i < F; i++) // iterate over the members of the family
{
total_price += solveKnapsack(P, W, M[i], N); // get maximum price by solving 0-1 knapsack for the current family member
}
return total_price;
}

int main()
{
ifstream infile; // input file stream
infile.open("shopping.txt"); // open input file
ofstream outfile; // output file stream
outfile.open("shopping.out"); // open output file
int T; // number of test cases
infile >> T; // read T from input file
for (int i = 0; i < T; i++) // for each test case
{
int N; // number of items
infile >> N; // read N from input file
int P[N], W[N]; // array to store P and W for the test case
for (int j = 0; j < N; j++)
{
infile >> P[j]; // fill P[j]
infile >> W[j]; // fill W[j]
}
int F; // number of family members
infile >> F; // read F from input file
int M[F]; // array to store M for the test case
for (int j = 0; j < F; j++)
{
infile >> M[j]; // fill M[j]
}
outfile << solve(P, W, M, N, F) << endl; // write solution for test case into output file
}
infile.close(); // close input file
outfile.close(); // close output file
return 0;
}

/*
************************************************************************************
extra.cpp
************************************************************************************
*/

#include <iostream>
#include <fstream>
#include <string>
#include <stdio.h>

using namespace std;

int solveKnapsack(int P[],int W[],int selected[],int M,int N) // solves an 0-1 knapsack problem
{
int K[N + 1][M + 1], i, w; // K[i][w] stores the maximum value obtained considering items from 0 to i, with a maximum weight limit of w
int E[N + 1][M + 1]; // E[i][w] keeps track of whether item i was included in the calculation of K[i][w]
for (i = 0; i <= N; i++) // iterate over all the items
{
for (w = 0; w <= M; w++) // iterate over the range of weights
{
E[i][w] = 0; // set default to not taken
if (i == 0 || w == 0) // if number of items or maximum weight allowed is zero
K[i][w] = 0; // set K[i][w] to 0
else if(W[i-1]<=w) // if weight of current item is lesser than the maximum allowed weight
{
int k1 = P[i - 1] + K[i - 1][w - W[i - 1]]; // new value if item is included
int k2 = K[i - 1][w]; // new value if item is excluded
if(k1>k2) // if including item is more profitable
{
K[i][w] = k1; // set value to value after including the current item
E[i][w] = 1; // mark the current item as taken
}
else
{
K[i][w] = k2; // set the value to value after excluding the current item
}
}
else
K[i][w] = K[i - 1][w]; // current item cannot be included
}
}
i = N; // start from the final item
w = M; // set current weight to M for backtracking
while(i>0&&w>=0) // Backtracking
{
if(E[i][w]==1) // if current item at i taken
{
selected[i-1] = 1; // mark selected to true
w -= W[i-1]; // decrease the weight by the weight of the selected item
i--; // move to next item
}
else
i--; // move to next item
}
return K[N][M]; // return K[N][M] as the solution
}

void solve(int P[],int W[],int M[],int N,int F,ofstream &out)
{
int total_price = 0,i,j; // accumulates the total price
int selected[F][N];
for (i = 0; i < F; i++) // iterate over the members of the family
{
for (j = 0; j < N;j++)
selected[i][j] = 0;
total_price += solveKnapsack(P, W, selected[i], M[i], N); // get maximum price by solving 0-1 knapsack for the current family member
}
out << "Total Price " << total_price << endl; // write total price to output file
out << "Member Items:" << endl;
for (i = 0; i < F; i++) // iterate over the members of the family
{
out << i + 1 << ": "; // write member number to the output file
for (j = 0; j < N; j++) // iterate over the items
{
if(selected[i][j]==1) // if for that member, that item is taken
out << j + 1 << " "; // write the item number to the output file
}
out << endl; // write new line to seperate next member
}
}

int main()
{
ifstream infile; // input file stream
infile.open("shopping.txt"); // open input file
ofstream outfile; // output file stream
outfile.open("extra.out"); // open output file
int T,i,j; // number of test cases
infile >> T; // read T from input file
for (i = 0; i < T; i++) // for each test case
{
int N; // number of items
infile >> N; // read N from input file
int P[N], W[N]; // array to store P and W for the test case
for (j = 0; j < N; j++)
{
infile >> P[j]; // fill P[j]
infile >> W[j]; // fill W[j]
}
int F; // number of family members
infile >> F; // read F from input file
int M[F]; // array to store M for the test case
for (j = 0; j < F; j++)
{
infile >> M[j]; // fill M[j]
}
solve(P, W, M, N, F, outfile); // write solution for test case into output file
}
infile.close(); // close input file
outfile.close(); // close output file
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.