1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #include <iostream> #include <sstream> std::stringstream ss(std::stringstream::out); // h - has how many unit stock // p - profit // bp - best profit void dfs(std::string t, std::string& s, double* P, int x, int y, int h, double p, double &bp) { if(x == y) { if(p > bp) { bp = p; s = t; } } else { if(h > 0) { // have stock can sell ss.clear(); ss.str(""); ss << P[x]; std::string sell = ss.str() + " sell\n"; dfs(t + sell, s, P, x + 1, y, 0, p + h * P[x], bp); } // buy ss.clear(); ss.str(""); ss << P[x]; std::string buy = ss.str() + " buy\n"; dfs(t + buy, s, P, x + 1, y, h + 1, p - P[x], bp); // pass ss.clear(); ss.str(""); ss << P[x]; std::string pass = ss.str() + " pass\n"; dfs(t + pass, s, P, x + 1, y, h, p, bp); } } int main() { double prices[8] = {55.39, 109.23, 48.29, 81.59, 81.58, 105.53, 94.45, 12.24}; double bestTotalProfit = 0.0; std::string ans, tmp; dfs(tmp, ans, prices, 0, 8, 0, 0.0, bestTotalProfit); std::cout << bestTotalProfit << std::endl; std::cout << ans; return 0; } |
Direct link: https://paste.plurk.com/show/414616