Question

Acme Super Store is having a contest to give away shopping sprees to lucky families. If...

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.

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.

In python:

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

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

Homework Answers

Answer #1

#include<iostream>

#include<fstream>

#include<vector>

#include<algorithm>

using namespace std;

int KDP(int[], int[], int, int, vector<int>&);

int max(int, int);

int main()

{

int T;   

int n;   

int PRICE[100];   

int WEIGHT[100];   

int F;   

int M = 0;   

vector<vector<int> > vec(200);

ifstream IP;

ofstream OP;

IP.open("shopping.txt");

if (!IP.is_open())

{

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

return 1;

}

OP.open("results.txt");

if (!OP.is_open())

{

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

return 1;

}

IP >> T;

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

{

IP >> n;

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

{

IP >> PRICE[i];

IP >> WEIGHT[i];

}

int maxTPrice = 0;

IP >> F;

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

{

IP >> M;

maxTPrice = maxTPrice + KDP(WEIGHT, PRICE, n, M, vec[j]);

}

OP << "Total Price " << maxTPrice << endl;

OP << "Member Items" << endl;

cout << "Total Price " << maxTPrice << endl;

cout << "Member Items" << endl;

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

{

sort(vec[t].begin(), vec[t].end());

OP << t + 1 << ":";

cout << t + 1 << ":";

for (int s = 0; s<vec[t].size(); s++)

{

OP << vec[t][s] << " ";

cout << vec[t][s] << " ";

}

cout << endl;

OP << endl;

}

}

IP.close();

OP.close();

return 0;

}

int KDP(int WEIGHT[], int PRICE[], int n, int M, vector<int> &v)

{

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

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 (WEIGHT[i - 1] <= w)

{

K[i][w] = max(PRICE[i - 1] + K[i - 1][w - WEIGHT[i - 1]], K[i - 1][w]);

}

else

{

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

}

}

}

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

{

v.push_back(i);

res = res - PRICE[i - 1];

w = w - WEIGHT[i - 1];

}

}

return K[n][M];

}

int max(int a, int b)

{

if (a > b)

return a;

else

return b;

}

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Create a ShoppingCart class in java that simulates the operation of a shopping cart. The ShoppingCart...
Create a ShoppingCart class in java that simulates the operation of a shopping cart. The ShoppingCart instance should contain a BagInterface implementation that will serve to hold the Items that will be added to the cart. Use the implementation of the Item object provided in Item.java. Note that the price is stored as the number of cents so it can be represented as an int (e.g., an Item worth $19.99 would have price = 1999). Your shopping cart should support...
This program extends the earlier "Online shopping cart" program. (Consider first saving your earlier program). Extend...
This program extends the earlier "Online shopping cart" program. (Consider first saving your earlier program). Extend the ItemToPurchase class per the following specifications              Private fields string itemDescription - Initialized in default constructor to "none" Parameterized constructor to assign item name, item description, item price, and itemquantity (default values of 0).             Public instance member methods setDescription() mutator & getDescription() accessor (2 pts) printItemCost() - Outputs the item name followed by the quantity, price, and subtotal printItemDescription() - Outputs the...
You will write a program that loops until the user selects 0 to exit. In the...
You will write a program that loops until the user selects 0 to exit. In the loop the user interactively selects a menu choice to compress or decompress a file. There are three menu options: Option 0: allows the user to exit the program. Option 1: allows the user to compress the specified input file and store the result in an output file. Option 2: allows the user to decompress the specified input file and store the result in an...
USING C++. The following divide-and-conquer algorithm is proposed for finding the simultaneous maximum and minimum: If...
USING C++. The following divide-and-conquer algorithm is proposed for finding the simultaneous maximum and minimum: If there is one item, it is the maximum and minimum, and if there are two items, then compare them, and in one comparison you can find the maximum and minimum. Otherwise, split the input into two halves, divided as evenly as possibly (if N is odd, one of the two halves will have one more element than the other). Recursively find the maximum and...
Java please. Need to use a linked list only. Many people have used pulling petals off...
Java please. Need to use a linked list only. Many people have used pulling petals off roses and tossing them in the air to determine if someone loves them or not. Your sister wants to use roses to determine which one of several suitors she will let take her to the prom. A linked list can be used to represent the prom date suitors. Write a program to simulate her decision and determine her prom date. The simulation will work...
In python Please The general elections are over, now is the time to count the votes...
In python Please The general elections are over, now is the time to count the votes and find out who will take the reins of this country. There are c (2 <= c <= 6) candidates and m (1 <= m <= 74) voting regions. Given the number of votes for each candidate in each municipality, determine which candidate is the winner (the one with the most votes). Input Format The first line of input contains an integer T (1...
**[70 pts]** You will be writing a (rather primitive) online store simulator. It will have these...
**[70 pts]** You will be writing a (rather primitive) online store simulator. It will have these classes: Product, Customer, and Store. All data members of each class should be marked as **private** (a leading underscore in the name). Since they're private, if you need to access them from outside the class, you should do so via get or set methods. Any get or set methods should be named per the usual convention ("get_" or "set_" followed by the name of...
C Program Write a program to count the frequency of each alphabet letter (A-Z a-z, total...
C Program Write a program to count the frequency of each alphabet letter (A-Z a-z, total 52 case sensitive) and five special characters (‘.’, ‘,’, ‘:’, ‘;’ and ‘!’) in all the .txt files under a given directory. The program should include a header count.h, alphabetcount.c to count the frequency of alphabet letters; and specialcharcount.c to count the frequency of special characters. Please only add code to where it says //ADDCODEHERE and keep function names the same. I have also...
IN JAVA!! You may be working with a programming language that has arrays, but not nodes....
IN JAVA!! You may be working with a programming language that has arrays, but not nodes. In this case you will need to save your BST in a two dimensional array. In this lab you will write a program to create a BST modelled as a two-dimensional array. The output from your program will be a two-dimensional array.   THEN: practice creating another array-based BST using integers of your choice. Once you have figured out your algorithm you will be able...
Program Description A local company has requested a program to calculate the cost of different hot...
Program Description A local company has requested a program to calculate the cost of different hot tubs that it sells. Use the following instructions to code the program: File 1 - HotTubLastname.java Write a class that will hold fields for the following: The model of the hot tub The hot tub’s feature package (can be Basic or Premium) The hot tub’s length (in inches) The hot tub’s width (in inches) The hot tub’s depth (in inches) The class should also...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT