cpp/dynamic_prog/maxprod

Viewing cpp/dynamic_prog/maxprod_memo 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

Define a memoized recursive function to compute <i>maxprod(N)</i>.

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 <iomanip>
#include <vector>
using namespace std;

double maxprod(int n, vector<double>& memory) {
// check if answer was already computed
if (\[memory[n] != 0]\)
return \[memory[n]]\;

// else save answer
if (\[n <= 3]\)
memory[n] = \[n]\;
else
memory[n] = \[max(2*maxprod(n-2, memory), 3*maxprod(n-3, memory))]\;

return memory[n];
}

int main(int argc, char* argv[]) {
int N = atoi(argv[1]);
vector<double> memory(N+1, \[0]\); // sets initial value for vector
cout << setprecision(20) << maxprod(N, memory) << 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 [{}]

[
{"args": ["6"]},
{"args": ["7"]},
{"args": ["8"]},
{"args": ["20"]},
{"args": ["60"]},
{"args": ["100"]},
{"args": ["101"]},
{"args": ["102"]},
{"args": ["500"]},
{"args": ["1812"]}
]

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	Define a memoized recursive function to compute <i>maxprod(N)</i>.
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 <iomanip> #include <vector> using namespace std; double maxprod(int n, vector<double>& memory) { // check if answer was already computed if (\[memory[n] != 0]\) return \[memory[n]]\; // else save answer if (\[n <= 3]\) memory[n] = \[n]\; else memory[n] = \[max(2maxprod(n-2, memory), 3maxprod(n-3, memory))]\; return memory[n]; } int main(int argc, char* argv[]) { int N = atoi(argv[1]); vector<double> memory(N+1, \[0]\); // sets initial value for vector cout << setprecision(20) << maxprod(N, memory) << 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 `[{}]`	[ {"args": ["6"]}, {"args": ["7"]}, {"args": ["8"]}, {"args": ["20"]}, {"args": ["60"]}, {"args": ["100"]}, {"args": ["101"]}, {"args": ["102"]}, {"args": ["500"]}, {"args": ["1812"]} ]
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'.