及时卖腐烂的苹果

Question

我对以下问题感到困惑.你有好主意吗？当然,强制所有排列可以解决问题.但是,有另一种方法吗？

假设你卖苹果,每个苹果都有一个相关的"腐烂时间",直到它不能再出售.

假设所有苹果都有一个独立的价格取决于它们的美学.价格是恒定的,直到苹果腐烂,然后它变为零.

卖苹果需要一些时间,因此你不能把它们全部卖掉,只能卖掉第一批苹果.

您应该以哪种顺序出售缓慢腐烂的苹果以最大化您的结果？

您是否有任何类型的文献可以提供帮助的提示？像运营研究或排队理论？

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 的评论，因为它解释了算法的正确性，而不仅仅是评论。

请注意，该解决方案的正确性主要取决于这样的观察：如果苹果的某个子集完全可以出售，那么它可以按到期时间升序出售。因此，如果您按到期时间按升序排列所有苹果，则您需要对每个苹果做出的唯一决定是现在出售还是根本不出售它

执行

这是 Python 中的一个简单的递归实现（可以很容易地记住多项式时间）：

该程序还解释了必须选择哪些苹果才能最大化结果：

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)

这输出：

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