*This is for programming in C++* The grocery list is below for reference. The se
ID: 3776966 • Letter: #
Question
*This is for programming in C++*
The grocery list is below for reference. The setup of the problem is to imagine you won a contest and you get a shopping spree. Think of an algorithm that will choose the most valuable items from that list but the only exception is that your cart cannot exceed 100 pounds and you have to buy whole items, not part of them. In other words, get your money's worth without exceeding 100 pounds. After that, you should have the following output:
The name and cost of each item
The total cost of all items in your cart
The total weight of all items in your cart
Here is the groceries list:
Bananas
1.31
0.99
Rib Eye Steak
2.55
14.96
Chicken Breast Value Pack
7.85
21.97
Dry Dog Food
20.00
14.99
Apples
2.50
3.49
Yogurt (Plain)
5.00
9.99
Bread (White)
2.00
1.59
Eggs (18 count)
2.00
2.99
Milk (Whole/Gallon)
1.00
4.29
Hamburger (Value Pack/90% Lean)
10.00
31.99
Deli Ham (Virginia)
3.00
21.49
Shrimp (Peel and Serve)
4.00
29.99
Canned Tomatoes (12 pack)
7.00
7.99
Cheese (American / 50 slices)
5.00
6.99
Bread (Hamburger Rolls / 24 count)
2.00
2.99
Tuna Fish (Canned albacore with Oil / 12 count)
6.00
9.99
Olive Oil (Extra Virgin)
5.00
19.99
Kidney Beans (Canned with Juice)
3.00
3.49
Orange Juice (100% with pulp)
3.00
5.99
Cranberry Juice
2.00
4.99
Energy Drink (24 count)
1.75
19.99
Batteries (AA / 100 count)
7.50
29.99
Pork Shoulder
4.50
12.99
Sausage (Brown and Serve)
2.00
4.99
Salmon (Fresh Caught / Sushi Grade)
3.50
64.99
Bread (Hot Dog Buns / 24 count)
2.00
2.49
Cottage Cheese
1.35
3.99
Bacon (Center Cut)
2.00
14.99
Cream Cheese (4 pack)
4.00
8.99
T-shirt of your local city
1.00
12.99
Dog Biscuits
2.00
3.99
Lobster (Fresh)
4.00
59.99
Oranges (10 count)
5.00
7.99
Canadian Bacon
2.00
9.99
Frozen Pizza (Pepperoni style / 3 pack)
3.00
12.99
Lettuce (Romaine)
3.00
6.99
Onions (Yellow)
3.00
4.49
Garlic (Fresh / 12 cloves)
1.45
3.99
Mushrooms (Portabella)
3.00
6.99
Dried Oregano
0.45
1.99
Cheese Curls
0.75
3.99
Soda (24 pack / Canned)
6.00
5.99
Sheet Cake (from in store bakery)
3.00
19.99
Frozen Pizza (Cheese style / 3 pack)
3.00
12.99
Green Peppers (Bell style)
3.00
6.99
Macaroni and Cheese (hot bar)
2.00
11.49
Frozen Turkey (Young)
19.49
28.76
Rice (White / Value Bag)
20.00
11.99
Green Curry (Jar)
0.45
4.29
London Broil
4.93
26.44
Butter (Salted)
2.00
4.29
Pound Cake (Frozen)
2.00
7.99
Bagels (Fresh / 12 count)
4.00
6.99
Pain Reliever (Generic brand / 100 count)
0.75
3.99
Hot Dogs (100% Beef)
4.50
9.99
Potato Chips
2.00
4.99
Ice (20 pound bag)
20.00
2.99
Gum (Peppermint / 5 pack)
0.75
2.49
Potatoes (Red Skin)
10.00
4.99
Shampoo
2.00
6.99
Explanation / Answer
Program:-
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<float> v, c;
std::vector<string> n;
vector< vector<float> > dp;
void selected(int i, int w)
{
if (i <= 0 || w <= 0) return;
int k = dp[i][w];
if (k != dp[i - 1][w]) {
cout << n[i] << " "<<v[i]<<" "<<c[i]<<""<<endl; // select!
selected(i - 1, w - c[i]); // capacity decreases
} else {
// move on to next item; capacity no change
selected(i - 1, w);
}
}
int main()
{
int size=100, no;
cout<<"The max size of the basket is 100 pound"<<endl;
cout<<"Enter the total number of items:-"<<endl;
cin >> no;
// sloted for easy array access; values won't be used.
c.push_back(-1);
v.push_back(-1);
n.push_back("null");
float weight, value;
string name;
for (int i = 0; i < no; i++) {
cout<<"Enter the name and vlaue and weight of item "<<i+1<<"respectively :-"<<endl;
cin >> name >>weight >> value;
n.push_back(name);
c.push_back(weight);
v.push_back(value);
}
dp.resize(no + 1, vector<float>(size + 1, 0));
for (int i = 1; i <= no; i++) { // i is scope of items in consideration
for (int w = 1; w <= size; w++) { // j is max size of bag
if (c[i] > w) {
dp[i][w] = dp[i - 1][w];
} else {
dp[i][w] = max (dp[i - 1][w], v[i] + dp[i - 1][w - c[i]]);
}
}
}
cout << "selected items: ";
selected(no, size);
}
++++++++++++++++++++++++++++++++++++++++++++++++++++
output:-akshay@akshay-Inspiron-3537:~/Chegg$ g++ 01knap.cpp
akshay@akshay-Inspiron-3537:~/Chegg$ ./a.out
The max size of the basket is 100 pound
Enter the total number of items:-
3
Enter the name and vlaue and weight of item 1respectively :-
chicken 50.00 60.00
Enter the name and vlaue and weight of item 2respectively :-
dryfood 100 120
Enter the name and vlaue and weight of item 3respectively :-
Pickel 60 40
selected items: dryfood 120 100
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.