 # Programming Problem: Calories & Money

Subject Computer Science C-Family Programming

## Question

This programming assignment is inspired by an article about a CEO spending \$30,000 at a fast-food restaurant, in this case Chipotle’s. The article wondered how it would be possible to spend that much, and if one could, how could one maximize the calorie content. This is really a famous computational problem - the knapsack problem - which is NP-hard, but solvable by dynamic programming for small enough target values.

Here we are given a series of menu items and a target amount W (cents). We want to know if it is possible to spend exactly W cents, and, if so, what is the minimum number of calories with which it is possible to do so. Each input will represent a single menu and have a single target value. The ﬁrst line of the input contains a number N, the number of menu items. The second line contains a target amount W. Each of the following N lines contain two integers and a string: V C S. V is the value (or cost) of the item, in cents; C is the number of calories for that item; and S (a string) is the name of the item.

Input sample:
6
1900
100 200 burrito
200 350 taco
400 500 chimi
150 300 horchata
500 650 torta
300 400 cola

Your output should provide the minimum number of calories on which it is possible to spend exactly W cents. If it is not possible to spend exactly W cents, then indicate “not possible” in your output. When it is possible to spend that amount, you will need to list the menu items chosen that add up to W cents. You should provide both an iterative implementation and a memoized one.   They will probably give the same output (but could be different).

RECURRENCE
Here is a basic form of a subproblem and recurrence: For a subproblem, we deﬁne MCAL[w] be the minimum number of calories on which it is possible to spend exactly w cents. For the recurrence, let’s ﬁrst denote the input by vectors v and c, where v[i] is the value (or cost) of menu item i, and c[i] is the calorie content of that menu item. Now we can write the recurrence as ⁃ if w<0, MCAL[w] = inﬁnity ⁃ if w=0, MCAL[w] = 0 ⁃ else, MCAL[w] = MIN { MCAL[w-v[i]] + c[i] : 1<= i <= n } You may want to alter the recurrence to make it easier to manipulate, but this is a simple form of it.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

#include <fstream>
#include <iostream>

using namespace std;

const int INFINITY = 1000000000;

// struct to describe menu item
{
int cost;
int cals;
char name;
};

void GetElements(MenuItem items[], int j, int n, int * usedItems)
{
int * elements = new int[n];
for (int i = 0; i < n; i++)
{
elements[i] = 0;
}
while (j >= 0)
{
int tmp = usedItems[j];
if (tmp == -1) break; // if the item is not on menu
elements[tmp] += 1;
j -= items[usedItems[j]].cost;
}
for (int i = 0; i < n; i++) //Print the result
{
if (elements[i] > 0)
{
cout<< items[i].name << " " << elements[i] << endl;
}
}
cout << endl;
delete[] elements;
}...

This is only a preview of the solution. Please use the purchase button to see the entire solution

## Related Homework Solutions

Programming Questions \$40.00
Programming
C++
Computer Science
Strings
Codes
Characters
Pointers
Buffer
CMYK Colors
Encoding
Issues
Compiler Errors
Assembly Language
Intel Machine
Lines
Symbols
Simple Sum Using C Programming Language \$10.00
Computer Science
Programming
Summation
Loops
Statements
Variables
Functions
Input
Output
Algorithms
Programming Problem: Skyline Buildings \$8.00
Programming
C++
Skyline Buildings
Computer Science
Codes
XOR
Algorithms
Implementations
Languages
Classes
Area
Maximum Values
Corresponding Elements
Constraints
Statements
Variables
The Simplistic Primary Predictor in C++ \$20.00
Computer Science
Programming
C++
Primary Predictor
Election Results
Factors
Candidates
States
Information
Commercials
Campaign
Calculations
Statements
Variables
Input
Output
C#: ShoppingCart App \$40.00
Visual
C#
Computer
Science
Shopping
Cart
Fill
Console
Application
How to Program
Pythagoras
Triples
Live Chats