algorithm - 及时卖烂苹果

Question

我对以下问题感到困惑。你有好主意吗？当然，暴力破解所有排列可以解决问题。但是，还有其他方法吗？

假设你卖苹果，每个苹果都有一个相关的“腐烂时间”，直到它不能再卖了。

还假设所有苹果都有一个单独的价格，这取决于它们的美学。价格不变，直到苹果烂掉，然后变成零。

卖一个苹果需要一定的时间，因此你不能卖掉所有苹果，只能卖前 k 个苹果。

您应该按什么顺序出售缓慢腐烂的苹果，以最大限度地提高 yield ？

您有什么提示可以帮助您了解哪种类型的文献吗？喜欢运筹学或排队论？

Answer 1

我认为一个简单的动态规划就可以了:

T(i, j) = 0 #if i>|apples|
T(i, j) = T(i+1, j) #if j/k >= rot(i)
T(i, j) = max(value(i) + T(i+1, j+1), T(i+1, j)) #if j/k < rot(i)

用T(i, j)表示卖出j个苹果后卖到第i个苹果的最大利润。

在每个 DP 步骤中，您必须在出售或不出售当前苹果之间做出最佳选择。如果到目前为止已售出的苹果数量 (j) 除以按时间单位可以销售的苹果数量 (k) 达到苹果的“腐烂时间”( rot(i))，不能卖。

这里的一个技巧是您必须先按“腐烂时间”对苹果进行排序。

---

正确性

我将在此处粘贴 Ilmari Karonen 的评论，因为它解释了算法的正确性，不应该只是评论。

Note that the correctness of this solution depends crucially on the observation that, if a certain subset of the apples can be sold at all, it can be sold in ascending order by expiry time. Thus, if you consider all the apples in ascending order by expiry time, the only decision you need to make for each apple is whether to sell it now or to not sell it at all

---

实现

这是一个简单的 Python 递归实现(可以很容易地记住多项式时间):

这个程序还解释了必须选择哪些苹果才能使结果最大化:

A = [(2, 3), (1, 1), (3, 4), (1, 2)]

def solve(A, k, i, j):
    if i>=len(A): return (0, [])
    ttr, value = A[i]
    if j/k >= ttr:
        return solve(A, k, i+1, j)
    else:
        answer, explanation = solve(A, k, i+1, j+1)
        return max((value+answer, [A[i]]+explanation), solve(A, k, i+1, j))

print solve(sorted(A), 1, 0, 0)

这个输出:

(9, [(1, 2), (2, 3), (3, 4)])