c++ - 计算最大利润的代码

Question

最近我遇到了this IARCS 网站中的问题。

我解决这个问题的方法就像 Ramu 在给定的一天必须进行交易或什么都不做，并且由于他只能保留 1 头水牛，如果他有 1 头，他必须出售，如果没有，则必须购买。如果我可以计算出所有可能的组合，我可以很容易地确定他的最高利润。但我的代码似乎不起作用，它提供的输出比预期的要高一点，有时还会卡在更大的测试用例中，在尝试了 3 天后，有人能指导我走正确的道路吗？

这是我的代码:

#include <iostream>

int bestTrade(int arr[], int size, bool toTrade, int visits, int day) {
  if (day < size - 1) {
    day = day + 1;
    if (visits > 0) {
      if (visits % 2 == 0) {
        int visitsT = visits - 1;
        int trade = bestTrade(arr, size, true, visitsT, day) - arr[day];
        int nothing = bestTrade(arr, size, false, visits, day);
        if (nothing > trade) {
          return nothing;
        } else {
          return trade;
        }
      } else {
        int visitsT = visits - 1;
        int trade = bestTrade(arr, size, true, visitsT, day) + arr[day];
        int nothing = bestTrade(arr, size, false, visits, day);
        if (nothing > trade) {
          return nothing;
        } else {
          return trade;
        }
      }
    } else {
      return 0;
    }
  } else {
    return 0;
  }
}
int main(int argc, char const* argv[]) {
  int n, k;
  std::cin >> n >> k;
  int market[n];
  for (int i = 0; i < n; i++) {
    std::cin >> market[i];
  }
  k = (k / 2) * 2;
  int maxProfitT = bestTrade(market, n, true, k--, 0);
  int maxProfitN = bestTrade(market, n, false, k, 0);
  if (maxProfitN > maxProfitT) {
    std::cout << maxProfitN << std::endl;
  } else {
    std::cout << maxProfitT << std::endl;
  }
  return 0;
}

Answer 1

对于与 dynamic programming 有关的任何问题，这样想:

如果你知道最多k的最大利润交易直到(i-1)th一天，你能算出最多k的最大利润吗？交易直到ith天？？

想想……答案是Yes !!!!

比如说，最大利润最多k交易直到(i-1)th天是best(k,i-1) .你需要找出best(k,i)对于任何 i<n .

如果您选择不在 i-th 上进行任何交易天，所以best(k,i)与 best(k,i-1) 相同.如果你确实想进行交易，那么best(k,i) = max(value[i] - value[j] + best[k-1][j]), j 从 0 到 i`

所以，最后 DP公式结果为:

best[k][i] = max(best[k][i-1], max(value[i] - value[j] + best[k-1][j]), j<i )

一个工作代码，你可以看看here

希望对您有所帮助!!!