cpp/dynamic_prog/starbucks Source

Viewing cpp/dynamic_prog/starbucks by daveagp@gmail.com. You have unsaved changes. Log in above to create, edit, preview and publish Websheets.

Property Value

Description
html markup
shown to student

This program should read from cin a data file of the format
<pre>
cardvalue
N
price1 price2 ... priceN
</pre>
where all values are integers. You have a gift card worth <tt>cardvalue</tt>,
and the store sells items costing <tt>price1</tt>, <tt>price2</tt>, ... <tt>priceN</tt>.
Print out the maximum amount that you can spend without exceeding <tt>cardvalue</tt>.
<p>
For example, if the input is
<pre>
100
5
40 23 88 32 20
</pre>
then the output should be <tt>95</tt>, which you can attain by buying the items worth 40, 23 and 32.

Epilogue
html markup
shown when solved

remove
Public permissions remove
Remarks
Comments, history, license, etc.

remove
Engine
Choices
json list of string, bool pairs
e.g. [["good", true], ["bad", false]]

Correct answer
Template / Reference solution

Template / Reference solution

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char* argv[]) {
// read the input
int cardvalue, N;
cin >> cardvalue >> N;
int price[N]; // bad style, VLA
for (int i=0; i<N; i++) cin >> price[i];

// declare the dynamic programming table
// first index: remaining cash
// second index: items left to consider
int best_spend[cardvalue+1][N+1]; // bad style, VLA

for (int limit=0; limit<=cardvalue; limit++) {
for (int items_left=0; items_left<=N; items_left++) {
// compute best_spend[limit][items_left]
int result = 0;
// try not buying this item
\[
if (items_left > 0)
result = max(result, best_spend[limit][items_left-1]);
]\
// try buying this item
\[
if (items_left > 0 && limit >= price[N-items_left]) {
int p = price[N-items_left];
result = max(result, p + best_spend[limit - p][items_left-1]);
}
]\
best_spend[limit][items_left] = result;
}
}
// print out entry for full card value and all items
cout << \[best_spend[cardvalue][N]]\ << endl;
}

Java test suite
See manual

C++ test suite
json list of stdin/args tests
e.g. [{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]
to just run once with no input use [{}]

[
{"stdin": "100\n5\n40 23 88 32 20"},
{"stdin": "200\n5\n40 23 88 32 20"},
{"stdin": "90\n5\n40 23 88 32 20"},
{"stdin": "10\n5\n40 23 88 32 20"},
{"stdin": "1000\n5\n40 23 88 32 20"},
{"stdin": "10000\n10\n1826 2048 1141 1386 455 1729 619 1287 1273 1569"},
{"stdin": "80000\n20\n12271 13721 22971 14621 35441 19951 27871 12441 33161 29551 13711 11711 13601 38691 12321 15351 26011 34292 16051 14190"}
]

C++ test suite
See manual

Forbidden substrings
json list of strings
e.g. ["for","while"]

remove
Solution visibility remove
Java imports
json list of importables
e.g. ["java.util.*"]

remove
Override Java classname
else defaults to
websheet name
remove
Dependent on other websheets?
json list of websheet names in this folder
e.g. ["DataStructure"]

remove
Is example?
i.e., just a demo
remove
Add compiler flag(s)
json list of flags
e.g. ["-Wno-unused-variable"]

remove
Remove default compiler flag(s)
json list of flags
see default_cppflags
e.g. ["-Wno-write-strings"]

remove

Property	Value
Description html markup shown to student	This program should read from cin a data file of the format <pre> cardvalue N price1 price2 ... priceN </pre> where all values are integers. You have a gift card worth <tt>cardvalue</tt>, and the store sells items costing <tt>price1</tt>, <tt>price2</tt>, ... <tt>priceN</tt>. Print out the maximum amount that you can spend without exceeding <tt>cardvalue</tt>. <p> For example, if the input is <pre> 100 5 40 23 88 32 20 </pre> then the output should be <tt>95</tt>, which you can attain by buying the items worth 40, 23 and 32.
Epilogue html markup shown when solved	remove
Public permissions	remove
Remarks Comments, history, license, etc.	remove
Engine
Choices json list of string, bool pairs e.g. `[["good", true], ["bad", false]]`
Correct answer
Template / Reference solution
Template / Reference solution	#include <algorithm> #include <iostream> #include <vector> using namespace std; int main(int argc, char* argv[]) { // read the input int cardvalue, N; cin >> cardvalue >> N; int price[N]; // bad style, VLA for (int i=0; i<N; i++) cin >> price[i]; // declare the dynamic programming table // first index: remaining cash // second index: items left to consider int best_spend[cardvalue+1][N+1]; // bad style, VLA for (int limit=0; limit<=cardvalue; limit++) { for (int items_left=0; items_left<=N; items_left++) { // compute best_spend[limit][items_left] int result = 0; // try not buying this item \[ if (items_left > 0) result = max(result, best_spend[limit][items_left-1]); ]\ // try buying this item \[ if (items_left > 0 && limit >= price[N-items_left]) { int p = price[N-items_left]; result = max(result, p + best_spend[limit - p][items_left-1]); } ]\ best_spend[limit][items_left] = result; } } // print out entry for full card value and all items cout << \[best_spend[cardvalue][N]]\ << endl; }
Java test suite See manual
C++ test suite json list of stdin/args tests e.g. `[{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]` to just run once with no input use `[{}]`	[ {"stdin": "100\n5\n40 23 88 32 20"}, {"stdin": "200\n5\n40 23 88 32 20"}, {"stdin": "90\n5\n40 23 88 32 20"}, {"stdin": "10\n5\n40 23 88 32 20"}, {"stdin": "1000\n5\n40 23 88 32 20"}, {"stdin": "10000\n10\n1826 2048 1141 1386 455 1729 619 1287 1273 1569"}, {"stdin": "80000\n20\n12271 13721 22971 14621 35441 19951 27871 12441 33161 29551 13711 11711 13601 38691 12321 15351 26011 34292 16051 14190"} ]
C++ test suite See manual
Forbidden substrings json list of strings e.g. `["for","while"]`	remove
Solution visibility	remove
Java imports json list of importables e.g. `["java.util.*"]`	remove
Override Java classname else defaults to websheet name	remove
Dependent on other websheets? json list of websheet names in this folder e.g. `["DataStructure"]`	remove
Is example? i.e., just a demo	remove
Add compiler flag(s) json list of flags e.g. `["-Wno-unused-variable"]`	remove
Remove default compiler flag(s) json list of flags see default_cppflags e.g. `["-Wno-write-strings"]`	remove

Optional properties:

Note: problems are open-source by default (see 'Public permissions'). Assumed license for open problems is Creative Commons 4.0 Attribution-ShareAlike unless specified in 'Remarks'.