面试问题：通过投资股票获得最大利润

Question

假设我们有M个硬币，我们想把它投资于股票。有 N 只股票，他可以投资一些非负整数。股票的利润 i 由二次函数给出：

A_iX_i² + B_iX_i

其中 X_i 是投资于股票 i 的整数金额。 (−1000 ≤ A_i ≤ −1) & (1 ≤ B_i ≤ 1000)

设计一个贪心算法来找出我们能赚到的最大金额？

不允许在股票中投入零星资金。我们可以投资不到M币。

Answer 1

给定函数Y = A_iX_i² + B_iX_i是二次函数。
对于约束，(−1000 ≤ Ai ≤ −1) 和 (1 ≤ Bi ≤ 1000) 投资可以表示为抛物线，如

注意三件事：

这些抛物线在 X'_i = -B_i / 2A[= 给出的点处有最大值23=]i
我们应该总是投资硬币 X_i 使得 0 ≤ X_i ≤ X'_i 产生利润。
对于给定数量的硬币k，最好将它们投资于最大值较大的投资。

那么贪心算法就是，

遍历所有 N 项投资，对于每项投资，我发现它对应 X_i = floor(X'_i ).
贪婪地接受所有这样的 k 投资（首先投资最大 X_i）使得 Sum(X_i) ≤ M 对于我所采取的所有这些。

这是让您入门的伪代码，

FIND_MAX(A, B, N, M):
    allProfits = [[]]
    for i = 1 to N:
        profit = []
        X = floor((-B[i]) / (2 * A[i]))
        profit.coins = X
        profit.index = i
        allProfits[i] =  profit
    Sort(allProfits)
    maxProfit = 0
    for j = N downto 1:
        if(M <= 0):
            break
        coins = min(allProfits[j].coins, M)
        i = allProfits[j].index
        maxProfit += (A[i] * coins * coins) + (B[i] * coins)
        M -= coins
    return maxProfit

Answer 2

在这种情况下，贪心算法确实提供了最佳解决方案。

重点是，如果对于给定的股票 x 个硬币已经投入，那么下一次花费的预期收益等于：

next_gain = f(x+1) - f(x) = 2ax + a + b

由于a为负，此收益总是随着x已经投入的硬币数量减少。迂腐地说，增益函数是凹的。

那么很容易证明，最优解是一个个花掉硬币，寻找最大next_gain的股票。这可以用 max_heap 来实现，导致复杂度 O(M logN).

如果M非常大，那么应该预见其他解决方案，例如基于拉格朗日函数。在这种情况下会涉及更多的数学。正如您提到的，您正在寻找一个贪婪的解决方案，我认为这个贪婪的解决方案足够快。

这是 C++ 中的代码。应该很容易转换为任何具有最大堆的代码。

输出：

Profit = 16


#include <iostream>
#include <vector>
#include <queue>

struct Stock {
    int index;
    int n_bought;
    int next_gain;
    Stock (int i, int n, int gain) : index(i), n_bought(n), next_gain (gain) {};
    friend operator< (const Stock& x, const Stock& y) {return x.next_gain < y.next_gain;};
};

long long int profit (std::vector<int>& A, std::vector<int>& B, int M) {
    int n = A.size();
    if (n != B.size()) exit (1);
    std::priority_queue<Stock> candidates;
    
    for (int i = 0; i < n; ++i) {
        int gain = A[i] + B[i];
        if (gain > 0) candidates.emplace(Stock(i, 0, gain));
    }
    long long int sum = 0.0;
    int coins = 0;
    while ((coins < M) &&(!candidates.empty())) {
        auto zebest = candidates.top();
        candidates.pop();
        coins++;
        sum += zebest.next_gain;
        zebest.n_bought++;
        int i = zebest.index;
        int gain = 2*A[i]*zebest.n_bought + A[i] + B[i];
        if (gain > 0) {
            zebest.next_gain = gain;
            candidates.push (zebest);
        }
    }
    return sum;
}

int main() {
    std::vector<int> A = {-2, -1, -2};
    std::vector<int> B = {3, 5, 10};
    int M = 3;

    auto ans = profit (A, B, M);
    std::cout << "Profit = " << ans << std::endl;
    return 0;
}

面试问题：通过投资股票获得最大利润

Interview Question: Maximum Profit by Investing in Stocks

algorithm

sorting

data-structures

greedy