有限窗口下的最优离散生产/供应调度

Question

我有一个大小为N的正整数P的列表。我有另一个相同大小的数字，C，但是C只能包含数字{-1,0,1}。我的目标是使i=1..N的和(Pi*Ci)最大化，但对于某些正k，-k =< sum(Ci) =< 0表示i=1..j，all j=1..N。

示例：

If k=1, P=[1,2,3,4], then C=[-1,0,0,1] with sum -1+4 = 3
If k=2, P=[1,2,3,4], then C=[-1,-1,1,1] with sum -1-2+3+4 = 4
If k=1, P=[10, 1, 8, 6, 7], then C=[0,-1,1,-1,1] with sum = -1+8-6+7 = 8

问题是，在给定任意k和P的情况下，寻找C的有效算法是什么？

注意，为了将其与实际问题联系起来:p表示生产成本或按时间间隔顺序供应的报酬，这取决于C中是否有a-1( produced )、0( depending )、1 (supply)，k是缓冲区的大小；所提供的东西必须是以前生产和填充在缓冲区中的。

Answer 1

有一个需要O(kN)时间的动态编程解决方案：

让REWARD(i,n)是可以实现的索引1...i的最佳奖励，它可以将n项完全保留在缓冲区中，如果无法处理将n项留在缓冲区中的索引1...i，则让REWARD(i,n) = -infinity处理。

例如，REWARD(1,n)是0表示n==0，-P[1]表示n==1，-infinity则是其他。

现在，给定所有REWARD(i,n)的n，很容易计算出所有n的REWARD(i+1,n)。这允许我们使用一种自下而上的动态编程方法，通过N矩阵填充N到REWARD(N,k)。

最大的回报是最高的REWARD(N,0)，因为如果n>0，我们总是可以通过提供缓冲项找到更好的解决方案。为了产生C，我们将返回到REWARD(N,0)所采取的步骤，根据我们所做的操作，在C中填充{0,1,-1}。