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

Question

给定一个维度为

V

的矩阵

m × n

，其中每个元素代表农产品市场连续 n 天的 m 种不同蔬菜种子的价格。此外，您还会得到一个整数

t (1 ≤ n)

，这是您可以在矩阵

V

中执行的最大交易数量。现在打印一个最多 t 笔交易的序列，每笔交易都涉及蔬菜种子的购买和销售，在交易种子后产生最大的利润。请注意，您必须在出售前购买种子，但您只能在出售日或之后购买另一颗（或相同的）种子。如果您无法通过出售种子获得任何利润，请打印

(0,0,0,0)

，否则在返回总利润值之前打印这样的元组列表

[(seed type index, buy day index, sell day index, profit yield)...]

。

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

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

#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;
}

Answer 1

这是我到目前为止的想法，我还没有时间实现和测试：动态程序的每个单元格可以有两种概念状态：买入或卖出。

如果是购买：

dp[row]["buy"][col] =
  -price + (
    max(dp[any_row]["sell"][col'])
      where col' < col - c
    or 0 if none
  )

我们可以将最好的

max(dp[any_row]["sell"][col'])

保留到

col - c - 1

以供查找。

如果是卖出：

dp[row]["sell"][col] =
  price + max(dp[row]["buy"][col'])
    where col' < col
or 0 if none

我们可以将每行最好的

max(dp[row]["buy"][col']

保留到

col - 1

。

由于我们总是查看前面的列，因此我们可以逐列处理矩阵。

结果应该是：

max(dp[any_row]["sell"][col])
  where col ≤ last column
or 0 if none

后者我们可以边走边保存。