如何在O(mnt)复杂度下记录种子交易的最大利润交易序列？

云原生阿岚

2026-7-10

问题描述

给定一个m×n的矩阵V，其中每个元素代表农产品市场中m种不同蔬菜种子在n个连续交易日的价格。此外给定整数t（1≤t≤n），即允许的最大交易次数。要求输出能获得最大利润的最多t次交易序列，每次交易包含种子类型索引、买入日索引、卖出日索引、利润额。交易规则：必须先买入再卖出，且只能在上一次卖出当天或之后买入新的种子（可以是同一种）。若无法获得正利润，输出(0,0,0,0)；否则先输出交易元组列表，再输出总利润。

示例

输入：
t = 3（最多3次交易）
V = [[2, 6, 3], [4, 2, 8]]

输出：
[(0,0,1,4),(1,1,2,6)]
10

解释：买入种子0在第0天，第1天卖出，利润4；买入种子1在第1天，第2天卖出，利润6，总利润10（只用了2次交易，未达上限3次）。

当前困境

现有C++代码仅能计算并返回最大利润值，无法输出对应利润的交易序列。需要在**保持时间复杂度O(m×n×t)**的前提下，实现交易序列的输出功能。

现有代码

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

解决方案

要输出交易序列，核心是在动态规划过程中记录每个状态的最优决策路径，之后通过回溯还原交易步骤。以下是修改后的代码，保持原时间复杂度：

修改后的完整代码

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <climits>

using namespace std;

// 记录DP状态的来源，用于回溯交易路径
struct DPState {
    int prev_trans;    // 上一次的交易次数
    int prev_day;      // 上一个天数
    int seed_idx;      // 当前交易的种子索引
    int buy_day;       // 当前交易的买入日
    bool is_hold;      // 是否是延续前一天的无交易状态
};

// 回溯生成交易序列
vector<tuple<int, int, int, int>> backtrack(
    const vector<vector<int>>& profits_table,
    const vector<vector<DPState>>& dp_states,
    const vector<vector<int>>& V,
    int t, int n) {
    
    vector<tuple<int, int, int, int>> transactions;
    int curr_trans = t;
    int curr_day = n - 1;

    while (curr_trans > 0 && curr_day >= 0) {
        const DPState& state = dp_states[curr_trans][curr_day];
        
        // 如果当前状态是完成了一笔交易
        if (!state.is_hold) {
            int seed = state.seed_idx;
            int buy = state.buy_day;
            int sell = curr_day;
            int profit = V[seed][sell] - V[seed][buy];
            transactions.emplace_back(seed, buy, sell, profit);
            // 跳转到这笔交易之前的状态
            curr_trans = state.prev_trans;
            curr_day = state.buy_day - 1;
        } else {
            // 延续前一天的无交易状态，直接往前跳一天
            curr_day = state.prev_day;
        }
    }

    // 反转得到从早到晚的交易顺序
    reverse(transactions.begin(), transactions.end());
    return transactions;
}

// 返回交易序列和总利润
pair<vector<tuple<int, int, int, int>>, int> seeding(const vector<vector<int>>& V, int t) {
    int m = V.size();
    int n = V[0].size();

    // DP表：profits_table[i][j] = 前j天做i次交易的最大利润
    vector<vector<int>> profits_table(t + 1, vector<int>(n, 0));
    // 状态记录表：每个DP状态的决策来源
    vector<vector<DPState>> dp_states(t + 1, vector<DPState>(n));

    // 初始化0次交易的状态：所有天都无利润，延续前一天
    for (int j = 0; j < n; ++j) {
        dp_states[0][j] = {0, j > 0 ? j-1 : -1, -1, -1, true};
    }

    for (int i = 1; i <= t; ++i) {
        // max_diff[k] = max(前i-1次交易在d天的利润 - V[k][d])，d < j（买入种子k的最优时机）
        vector<int> max_diff(m, INT_MIN);
        vector<int> buy_day(m, -1);

        // 第0天无法完成交易，初始化状态
        profits_table[i][0] = 0;
        dp_states[i][0] = {i, -1, -1, -1, true};

        for (int j = 1; j < n; ++j) {
            // 默认延续前一天的状态
            profits_table[i][j] = profits_table[i][j-1];
            dp_states[i][j] = {i, j-1, -1, -1, true};

            // 更新买入种子k的最优时机（考虑在j-1天买入）
            for (int k = 0; k < m; ++k) {
                int curr_val = profits_table[i-1][j-1] - V[k][j-1];
                if (curr_val > max_diff[k]) {
                    max_diff[k] = curr_val;
                    buy_day[k] = j-1;
                }
            }

            // 计算当天卖出各种子的利润，更新最优解
            for (int k = 0; k < m; ++k) {
                if (max_diff[k] == INT_MIN) continue;
                int current_profit = V[k][j] + max_diff[k];
                if (current_profit > profits_table[i][j]) {
                    profits_table[i][j] = current_profit;
                    // 记录完成这笔交易的状态信息
                    dp_states[i][j] = {i-1, buy_day[k], k, buy_day[k], false};
                }
            }
        }
    }

    int total_profit = profits_table[t][n-1];
    vector<tuple<int, int, int, int>> transactions;

    if (total_profit <= 0) {
        transactions.emplace_back(0, 0, 0, 0);
    } else {
        transactions = backtrack(profits_table, dp_states, V, t, n);
    }

    return {transactions, total_profit};
}

int main() {
    vector<vector<int>> V = {{2, 6, 3}, {4, 2, 8}};
    int t = 3;

    auto [transactions, total_profit] = seeding(V, t);

    // 输出交易序列
    cout << "[";
    for (size_t i = 0; i < transactions.size(); ++i) {
        auto [seed, buy, sell, profit] = transactions[i];
        cout << "(" << seed << "," << buy << "," << sell << "," << profit << ")";
        if (i != transactions.size() - 1) {
            cout << ",";
        }
    }
    cout << "]" << endl;

    // 输出总利润
    cout << total_profit << endl;

    return 0;
}

核心改动说明

加个结构体存决策路径：定义DPState结构体，专门记录每个DP状态的来源——是延续前一天的无交易状态，还是完成了一笔交易，同时记下交易的种子、买入日等关键信息，方便后续倒推。
跟踪买入的具体日子：原来的max_diff只存买入的最优利润，现在同步记录对应的买入日，确保卖出时能直接定位买入时间点。
倒推生成交易序列：从最后一天、最多交易次数的状态往回走，根据DPState的记录还原每一笔交易，最后反转得到从早到晚的交易顺序。
处理无利润边界：如果总利润≤0，直接输出(0,0,0,0)。

时间复杂度分析

动态规划部分：三层循环（交易次数t × 天数n × 种子数m），时间复杂度O(m×n×t)，与原代码一致。
回溯部分：最多遍历t次交易和n天，时间复杂度可忽略不计。

内容的提问来源于stack exchange，提问作者WolfgangBagdanow

如何在O(mnt)复杂度下记录种子交易的最大利润交易序列？

问题描述 #

示例 #

当前困境 #

现有代码 #

解决方案 #

修改后的完整代码 #

核心改动说明 #

时间复杂度分析 #