在返回有效交易的值之前打印元组序列

Question

给定一个V维度矩阵m \xc3\x97 n，其中每个元素代表农产品市场连续 n 天 m 种不同蔬菜种子的价格。此外，您还会得到一个整数t (1 \xe2\x89\xa4 n)，它是您可以在矩阵中执行的最大交易数V。现在打印一个最多 t 笔交易的序列，每笔交易都涉及蔬菜种子的购买和销售，在交易种子后产生最大的利润。请注意，您必须在出售前购买种子，但您只能在出售日或之后购买另一颗（或相同的）种子。如果您无法通过出售种子获得任何利润，请在返回总利润值之前打印(0,0,0,0)或打印这样的元组列表。[(seed type index, buy day index, sell day index, profit yield)...]

\n

Example:\nt = 3 (at most 3 transactions are allowed)\nV = [[2, 6, 3],\n     [4, 2, 8]]\n\nResult:\nTotal profit yield returned is 10. Tuples: Buy seed type 0 on day 0 then sell \nit on day 1 which gives value of 4 (6-4). Then, buy seed type 1 on day 1 then\nsell on day 2 which gives value of 6 (8-2). \n\nThe final output should be:\n[(0,0,1,4),(1,1,2,6)] \n10\n

\n

目前，代码给出了总利润收益率值。我不知道如何打印元组来打印所有给出 10 的交易。我需要保持 O(m n t ) 的时间复杂度。任何指导将不胜感激。

\n

Example:\nt = 3 (at most 3 transactions are allowed)\nV = [[2, 6, 3],\n     [4, 2, 8]]\n\nResult:\nTotal profit yield returned is 10. Tuples: Buy seed type 0 on day 0 then sell \nit on day 1 which gives value of 4 (6-4). Then, buy seed type 1 on day 1 then\nsell on day 2 which gives value of 6 (8-2). \n\nThe final output should be:\n[(0,0,1,4),(1,1,2,6)] \n10\n

\n

Answer 1

虽然我对此仍然有一些疑问。就像我不能 100% 确定什么是或不是交易，以及其他一些事情，但以下内容应该可以满足您 90% 以上的需求。
\n对于代码的冗长，我提前表示歉意。

\n

#ifndef NODE_HPP\n#define NODE_HPP\n#include <compare>\n#include <memory>\n\nenum class operation\n{\n  buy  = 0,\n  sell = 1,\n  hold = 2,\n};\n\nstruct node\n{\n  operation                   op{};\n  std::shared_ptr<const node> parent{};\n  int                         value{};\n  int                         type{};\n\n  auto                        operator<=>(const node& other) const\n  {\n    return profit() <=> other.profit();\n  }\n\n  int calculate() const\n  {\n    switch (op)\n    {\n      case operation::buy:\n      {\n        return -value;\n      }\n      case operation::sell:\n      {\n        return value;\n      }\n      case operation::hold:\n      {\n        return 0;\n      }\n      default:\n      {\n        return 0;\n      }\n    }\n  }\n\n  int profit() const\n  {\n    if (parent == nullptr)\n    {\n      return value;\n    }\n    return calculate() + parent->profit();\n  }\n\n  std::string op_to_string() const\n  {\n    switch (op)\n    {\n      case operation::buy:\n      {\n        return "Buy";\n      }\n      case operation::sell:\n      {\n        return "Sell";\n      }\n      case operation::hold:\n      {\n        return "Hold";\n      }\n    }\n  }\n\n  std::string print() const\n  {\n    if (parent == nullptr)\n    {\n      return "";\n    }\n\n    return parent->print() + " " + op_to_string() + " " + std::to_string(value);\n  }\n};\n\n#endif  // NODE_HPP\n\n\n\n#ifndef FUNCS_HPP\n#define FUNCS_HPP\n#include <array>\n\n#include "node.hpp"\n\nstd::shared_ptr<const node> find_best(const std::array<std::array<int, 3>, 2>& prices, int max_trans);\n\nstd::shared_ptr<const node> recurse_root(\n    const std::array<std::array<int, 3>, 2>& prices, int curr_trans,\n    int max_trans, int curr_day, std::shared_ptr<const node> parent);\n\nstd::shared_ptr<const node> sell(\n    const std::array<std::array<int, 3>, 2>& prices, int curr_trans,\n    int max_trans, int curr_day, std::shared_ptr<const node> parent);\n\nstd::shared_ptr<const node> buy(const std::array<std::array<int, 3>, 2>& prices,\n                                int curr_trans, int max_trans, int curr_day,\n                                std::shared_ptr<const node> parent, int type);\n\nstd::shared_ptr<const node> hold(\n    const std::array<std::array<int, 3>, 2>& prices, int curr_trans,\n    int max_trans, int curr_day, std::shared_ptr<const node> parent);\n\nstd::shared_ptr<const node> decide(\n    const std::array<std::array<int, 3>, 2>& prices, int curr_trans,\n    int max_trans, int curr_day, std::shared_ptr<const node> parent);\n\n#endif  // FUNCS_HPP\n\n\n#include "funcs.hpp"\n\n#include <iostream>\n\nstd::shared_ptr<const node> sell(\n    const std::array<std::array<int, 3>, 2>& prices, const int curr_trans,\n    const int max_trans, const int curr_day, std::shared_ptr<const node> parent)\n{\n  return recurse_root(\n      prices, curr_trans + 1, max_trans, curr_day,\n      std::make_shared<node>(node{ .op     = operation::sell,\n                                   .parent = parent,\n                                   .value  = prices[parent->type][curr_day],\n                                   .type   = parent->type }));\n}\n\nstd::shared_ptr<const node> buy(const std::array<std::array<int, 3>, 2>& prices,\n                                const int curr_trans, const int max_trans,\n                                const int                   curr_day,\n                                std::shared_ptr<const node> parent,\n                                const int                   type)\n{\n  return recurse_root(\n      prices, curr_trans, max_trans, curr_day + 1,\n      std::make_shared<node>(node{ .op     = operation::buy,\n                                   .parent = std::move(parent),\n                                   .value  = prices[type][curr_day],\n                                   .type   = type }));\n}\n\nstd::shared_ptr<const node> hold(\n    const std::array<std::array<int, 3>, 2>& prices, const int curr_trans,\n    const int max_trans, const int curr_day, std::shared_ptr<const node> parent)\n{\n  return recurse_root(prices, curr_trans, max_trans, curr_day + 1,\n                      std::make_shared<node>(node{ .op     = operation::hold,\n                                                   .parent = parent,\n                                                   .value  = 0,\n                                                   .type   = parent->type }));\n}\n\noperation find_last_op(std::shared_ptr<const node> parent)\n{\n  while (parent != nullptr && parent->op == operation::hold)\n  {\n    parent = parent->parent;\n  }\n\n  if (parent == nullptr)\n  {\n    return operation::sell;\n  }\n\n  return parent->op;\n}\n\nstd::shared_ptr<const node> decide(\n    const std::array<std::array<int, 3>, 2>& prices, const int curr_trans,\n    const int max_trans, const int curr_day, std::shared_ptr<const node> parent,\n    operation op)\n{\n  switch (op)\n  {\n    case operation::buy:\n    {\n      const auto h_result =\n          hold(prices, curr_trans, max_trans, curr_day, parent);\n      const auto s_result =\n          sell(prices, curr_trans, max_trans, curr_day, parent);\n      return std::max(h_result, s_result,\n                      [](const std::shared_ptr<const node>& a,\n                         const std::shared_ptr<const node>& b)\n                      { return a->profit() < b->profit(); });\n    }\n    case operation::sell:\n    {\n      auto result = hold(prices, curr_trans, max_trans, curr_day, parent);\n      for (int i = 0; i < static_cast<int>(prices.size()); ++i)\n      {\n        const auto b_result =\n            buy(prices, curr_trans, max_trans, curr_day, parent, i);\n        result = std::max(result, b_result,\n                          [](const std::shared_ptr<const node>& a,\n                             const std::shared_ptr<const node>& b)\n                          { return a->profit() < b->profit(); });\n      }\n      return result;\n    }\n    case operation::hold:\n    {\n      return decide(prices, curr_trans, max_trans, curr_day, parent,\n                    find_last_op(parent));\n    }\n  }\n}\n\nstd::shared_ptr<const node> decide(\n    const std::array<std::array<int, 3>, 2>& prices, const int curr_trans,\n    const int max_trans, const int curr_day, std::shared_ptr<const node> parent)\n{\n  return decide(prices, curr_trans, max_trans, curr_day, parent, parent->op);\n}\n\nstd::shared_ptr<const node> recurse_root(\n    const std::array<std::array<int, 3>, 2>& prices, const int curr_trans,\n    const int max_trans, const int curr_day, std::shared_ptr<const node> parent)\n{\n  if (curr_trans >= max_trans)\n  {\n    return parent;\n  }\n\n  if (curr_day >= static_cast<int>(prices[0].size()))\n  {\n    return parent;\n  }\n\n  return decide(prices, curr_trans, max_trans, curr_day, parent);\n}\n\nstd::shared_ptr<const node> find_best(\n    const std::array<std::array<int, 3>, 2>& prices, const int max_trans)\n{\n  return recurse_root(\n      prices, 0, max_trans, 0,\n      std::make_shared<const node>(node{ .op = operation::sell }));\n}\n\n

\n

然后可以这样调用

\n

#include <array>\n#include <iostream>\n\n#include "funcs.hpp"\n#include "node.hpp"\n\nint main()\n{\n\n  constexpr auto max_trans = 3;\n  auto           prices    = std::array<std::array<int, 3>, 2>{\n    { { 2, 6, 3 }, { 4, 2, 8 } }\n  };\n\n  const auto result = find_best(prices, max_trans);\n\n  std::cout << "\\n";\n  std::cout << result->profit();\n  std::cout << "\\n";\n  std::cout << result->print();\n  std::cout << "\\ndone!";\n}\n

\n

示例输出运行：

\n

10\n Buy 2 Sell 6 Buy 2 Sell 8 Hold 0\ndone!\xe2\x8f\x8e  \n

\n

您可以根据自己的喜好自定义打印消息，我没有将其放入您概述的格式（我有疑问的其他事情之一），但这样做是对打印功能的一个小修改。

\n

预先警告，我只在您提供的一个示例上对此进行了测试。从数组大小的硬编码中可以明显看出这一点。
\n我认为代码非常清晰，易于修改和识别可能出现的任何问题，我会查找您可能对此有的任何问题。

\n

希望这可以帮助！

\n