You are given a matrix V of dimensions m × n, where each element represents the prices of m different vegetables seeds for n consecutive days in a produce market. Furthermore, you are given an integer t (1 ≤ n), which is the max number of transaction you can perform in the matrix V. Now print a sequence of at most t transactions, each involving the purchase and sale of a vegetable seed, that yields the maximum profit after trading seeds. Note, you must buy a seed before selling, but you can only buy another (or same) seed on or after the sell day. If you can't get any profits from selling the seeds, print (0,0,0,0) else print a list of tuples like this [(seed type index, buy day index, sell day index, profit yield)...] before returning the total profit value.
Example:
t = 3 (at most 3 transactions are allowed)
V = [[2, 6, 3],
[4, 2, 8]]
Result:
Total profit yield returned is 10. Tuples: Buy seed type 0 on day 0 then sell
it on day 1 which gives value of 4 (6-4). Then, buy seed type 1 on day 1 then
sell on day 2 which gives value of 6 (8-2).
The final output should be:
[(0,0,1,4),(1,1,2,6)]
10
Currently, code gives total profit yield value. I can't figure out how to print tuples to print all the transactions that give 10. I need to maintain the time complexity of O(mnt). Any guidance will be appreciated.
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <climits>
using namespace std;
int seeding(vector<vector<int>> V, int t) {
int cols = V[0].size();
int rows = V.size();
vector<vector<int>> profits_table(t + 1, vector<int>(cols, 0));
vector<std::tuple<int, int, int, int>> tuple_result;
tuple_result.push_back(std::make_tuple(0, 0, 0, 0));
vector<int> max_diff(rows, 0);
int tempMax = 0;
for (int i = 1; i < t + 1; i++) {
for (int j = 0; j < rows; j++) {
max_diff[j] = -V[j][0];
}
for (int j = 1; j < cols; j++) {
for (int k = 0; k < rows; k++) {
tempMax = max(tempMax, V[k][j] + max_diff[k]);
profits_table[i][j] = max(profits_table[i][j - 1], tempMax);
max_diff[k] = max(max_diff[k], profits_table[i - 1][j] - V[k][j]);
//for (const auto& t : tuple_result)
// if (profits_table[i][j] > get<3>(t)) {
// tuple_result.push_back(make_tuple(i , distance(V[i].begin(), find(V[i].begin(), V[i].end(), abs(max_diff[k]))),
// j + 1, profits_table[i][j]));
// }
}
tempMax = 0;
}
}
// cout << "["
//for (const auto& tt : tuple_result)
//{
// cout << "(" << get<0>(tt) << ", " << get<1>(tt) << ", " <<
// get<2>(tt) << ", " << get<3>(tt) << ")" << endl;
//}
// cout << "]"
return profits_table[t][cols - 1];
}
int main()
{
vector<vector<int>> V = { {2, 6, 3},
{4, 2, 8 } };
int k = 3;
cout << seeding(V, k) << endl;
return 0;
}
While i still have questions about a few things about this. Like i'm not 100% sure what is or is not a transaction, as well as a few other things, but the following should get you 90%+ of what you're looking for.
I apologize in advance for the verbosity of the code.
#ifndef NODE_HPP
#define NODE_HPP
#include <compare>
#include <memory>
enum class operation
{
buy = 0,
sell = 1,
hold = 2,
};
struct node
{
operation op{};
std::shared_ptr<const node> parent{};
int value{};
int type{};
auto operator<=>(const node& other) const
{
return profit() <=> other.profit();
}
int calculate() const
{
switch (op)
{
case operation::buy:
{
return -value;
}
case operation::sell:
{
return value;
}
case operation::hold:
{
return 0;
}
default:
{
return 0;
}
}
}
int profit() const
{
if (parent == nullptr)
{
return value;
}
return calculate() + parent->profit();
}
std::string op_to_string() const
{
switch (op)
{
case operation::buy:
{
return "Buy";
}
case operation::sell:
{
return "Sell";
}
case operation::hold:
{
return "Hold";
}
}
}
std::string print() const
{
if (parent == nullptr)
{
return "";
}
return parent->print() + " " + op_to_string() + " " + std::to_string(value);
}
};
#endif // NODE_HPP
#ifndef FUNCS_HPP
#define FUNCS_HPP
#include <array>
#include "node.hpp"
std::shared_ptr<const node> find_best(const std::array<std::array<int, 3>, 2>& prices, int max_trans);
std::shared_ptr<const node> recurse_root(
const std::array<std::array<int, 3>, 2>& prices, int curr_trans,
int max_trans, int curr_day, std::shared_ptr<const node> parent);
std::shared_ptr<const node> sell(
const std::array<std::array<int, 3>, 2>& prices, int curr_trans,
int max_trans, int curr_day, std::shared_ptr<const node> parent);
std::shared_ptr<const node> buy(const std::array<std::array<int, 3>, 2>& prices,
int curr_trans, int max_trans, int curr_day,
std::shared_ptr<const node> parent, int type);
std::shared_ptr<const node> hold(
const std::array<std::array<int, 3>, 2>& prices, int curr_trans,
int max_trans, int curr_day, std::shared_ptr<const node> parent);
std::shared_ptr<const node> decide(
const std::array<std::array<int, 3>, 2>& prices, int curr_trans,
int max_trans, int curr_day, std::shared_ptr<const node> parent);
#endif // FUNCS_HPP
#include "funcs.hpp"
#include <iostream>
std::shared_ptr<const node> sell(
const std::array<std::array<int, 3>, 2>& prices, const int curr_trans,
const int max_trans, const int curr_day, std::shared_ptr<const node> parent)
{
return recurse_root(
prices, curr_trans + 1, max_trans, curr_day,
std::make_shared<node>(node{ .op = operation::sell,
.parent = parent,
.value = prices[parent->type][curr_day],
.type = parent->type }));
}
std::shared_ptr<const node> buy(const std::array<std::array<int, 3>, 2>& prices,
const int curr_trans, const int max_trans,
const int curr_day,
std::shared_ptr<const node> parent,
const int type)
{
return recurse_root(
prices, curr_trans, max_trans, curr_day + 1,
std::make_shared<node>(node{ .op = operation::buy,
.parent = std::move(parent),
.value = prices[type][curr_day],
.type = type }));
}
std::shared_ptr<const node> hold(
const std::array<std::array<int, 3>, 2>& prices, const int curr_trans,
const int max_trans, const int curr_day, std::shared_ptr<const node> parent)
{
return recurse_root(prices, curr_trans, max_trans, curr_day + 1,
std::make_shared<node>(node{ .op = operation::hold,
.parent = parent,
.value = 0,
.type = parent->type }));
}
operation find_last_op(std::shared_ptr<const node> parent)
{
while (parent != nullptr && parent->op == operation::hold)
{
parent = parent->parent;
}
if (parent == nullptr)
{
return operation::sell;
}
return parent->op;
}
std::shared_ptr<const node> decide(
const std::array<std::array<int, 3>, 2>& prices, const int curr_trans,
const int max_trans, const int curr_day, std::shared_ptr<const node> parent,
operation op)
{
switch (op)
{
case operation::buy:
{
const auto h_result =
hold(prices, curr_trans, max_trans, curr_day, parent);
const auto s_result =
sell(prices, curr_trans, max_trans, curr_day, parent);
return std::max(h_result, s_result,
[](const std::shared_ptr<const node>& a,
const std::shared_ptr<const node>& b)
{ return a->profit() < b->profit(); });
}
case operation::sell:
{
auto result = hold(prices, curr_trans, max_trans, curr_day, parent);
for (int i = 0; i < static_cast<int>(prices.size()); ++i)
{
const auto b_result =
buy(prices, curr_trans, max_trans, curr_day, parent, i);
result = std::max(result, b_result,
[](const std::shared_ptr<const node>& a,
const std::shared_ptr<const node>& b)
{ return a->profit() < b->profit(); });
}
return result;
}
case operation::hold:
{
return decide(prices, curr_trans, max_trans, curr_day, parent,
find_last_op(parent));
}
}
}
std::shared_ptr<const node> decide(
const std::array<std::array<int, 3>, 2>& prices, const int curr_trans,
const int max_trans, const int curr_day, std::shared_ptr<const node> parent)
{
return decide(prices, curr_trans, max_trans, curr_day, parent, parent->op);
}
std::shared_ptr<const node> recurse_root(
const std::array<std::array<int, 3>, 2>& prices, const int curr_trans,
const int max_trans, const int curr_day, std::shared_ptr<const node> parent)
{
if (curr_trans >= max_trans)
{
return parent;
}
if (curr_day >= static_cast<int>(prices[0].size()))
{
return parent;
}
return decide(prices, curr_trans, max_trans, curr_day, parent);
}
std::shared_ptr<const node> find_best(
const std::array<std::array<int, 3>, 2>& prices, const int max_trans)
{
return recurse_root(
prices, 0, max_trans, 0,
std::make_shared<const node>(node{ .op = operation::sell }));
}
Which can then be called like this
#include <array>
#include <iostream>
#include "funcs.hpp"
#include "node.hpp"
int main()
{
constexpr auto max_trans = 3;
auto prices = std::array<std::array<int, 3>, 2>{
{ { 2, 6, 3 }, { 4, 2, 8 } }
};
const auto result = find_best(prices, max_trans);
std::cout << "\n";
std::cout << result->profit();
std::cout << "\n";
std::cout << result->print();
std::cout << "\ndone!";
}
An example output run:
10
Buy 2 Sell 6 Buy 2 Sell 8 Hold 0
done!⏎
You can customize the print message to your heart's content, i didn't put it in the format you outlined (one of the other things i had a question about), but to do so is a small modification to the print function.
Forewarning, i only tested this on the one example you provided. As is probably obvious from the hard-coding of the array size.
I think the code is pretty clear and easy to modify and identify any issues, that may arise, and i'll look for any questions you may have about it.
Hope this helps!