算法备忘录化和回溯

Question

我正在为几个工作面试做准备，遇到了一些完全难住我的算法问题。我想知道你们中是否有人能够解释解决这个例子问题的策略或提供任何伪代码。

非常感谢！

问题： 你是一名自由承包商，你可以每周选择不同的工作。工作分为两组，ls和hs。如果你选择hs的工作，你必须在前一周做好准备，不接受任何工作。而ls工作则不需要这样的准备。

给定大小为n的数组l和h（其中n为周数），确定您的最佳工作计划。

因此，从下表中我理解：

╔═══╦══╦════╦════╦════╦═════╦═════╗
║   ║  ║ 0  ║ 1  ║ 2  ║  3  ║  4  ║
╠═══╬══╬════╬════╬════╬═════╬═════╣
║ l ║  ║ 30 ║  5 ║ 20 ║  25 ║ 500 ║
║ h ║  ║  0 ║ 50 ║ 70 ║ 100 ║ 110 ║
╚═══╩══╩════╩════╩════╩═════╩═════╝

最佳方案是NHNHL，奖励为650。但我不知道如何编写一个紧凑高效的算法来实现这一点。

- Detrivius Parker

---

在上述数组中，这些工作是顺序执行的，还是我可以按任意顺序执行它们？换句话说，我可以先在第2周做500号工作，然后再做30号工作等吗？ - Tyler Durden

@Detrivius 不要编辑你的问题以删除其中的内容。你目前有几个有效的答案回答了你的问题。 - Taryn

@bluefeet 我已经特别请求删除这个问题。 - Detrivius Parker

@DetriviusParker，目前你已经得到了关于这个问题的有效答案，那么你为什么想要将其删除呢？ - Taryn

Answer 1

每周你可以选择一个高压力工作或者一个低压力工作。如果你在第n周选择了一个低压力工作，那么最优解是前（n-1）周的最优解。如果你选择了一个高压力工作，那么最优解是前（n-2）周的最优解。这给出了动态规划的递归式：

F(n) = max(F_L(n), F_H(n))

F_L(n) = F(n-1) + x_L(n)

F_H(n) = F(n-2) + x_H(n)

其中x_L(n)和x_H(n)分别是第n周低压力工作和高压力工作的收益。如果你将F_L、F_H和F存储在数组中，并按照n的递增顺序进行构建，这就是动态规划，可以找到最优解的O(n)时间算法，直到第n周。显然，对于F(n)，你需要存储你在第n周选择的是高压力还是低压力工作，以便恢复最优工作序列。

- user2566092

Answer 2

另一种看待这个问题的方式是将数据建模为图。如果将权重建模为边，则可以使用Djikstra算法在图中找到最大路径。

我认为最简单的建模方法是使用我所称的前向聚合，这是一种动态规划。您从开始节点开始，并找到与起始节点相邻的节点的最大可能值和路径。然后计算相邻节点旁边的节点并依此类推，直到对所有可能的结束节点都有一个最大值。这显示了基本代码：

int xColumn = 1;
while( true ){
    if( xColumn > iNumberOfColumns ) break;

    // first do low stress row
    int xRow = 1; // low stress
    int iCurrentCellValue = aiValues[xColumn][xRow];
    if( xColumn == 1 ){
        aiMaximumSum[1][1] = iCurrentCellValue;
    } else {
        if( aiMaximumSum[xColumn - 1][1] > aiMaximumSum[xColumn][2] ){
            aiMaximumSum[xColumn][xRow] = iCurrentCellValue + aiMinimumSum[xColumn - 1][1];
        } else {
            aiMaximumSum[xColumn][xRow] = iCurrentCellValue + aiMinimumSum[xColumn - 1][2];
        }
    }

    // next do high stress row
    int xRow = 2; // low stress
    int iCurrentCellValue = aiValues[xColumn][xRow];
    if( xColumn == 1 || xColumn == 2 ){
        aiMaximumSum[1][1] = iCurrentCellValue;
    } else {
        if( aiMaximumSum[xColumn - 2][1] > aiMaximumSum[xColumn - 2][2] ){
            aiMaximumSum[xColumn][xRow] = iCurrentCellValue + aiMinimumSum[xColumn - 1][1];
        } else {
            aiMaximumSum[xColumn][xRow] = iCurrentCellValue + aiMinimumSum[xColumn - 1][2];
        }
    }

    xColumn++;
}

这段代码只是将每个单元格中可能的最大值存储起来。因此，在最后，您需要检查aiMaximumSum的最终列中的值，并且最高值将是答案值。该代码不会存储路径。要实现这一点，您需要有第二个数组，并为每个单元格存储路径（最大值是从L行还是H行来的）。

- Tyler Durden

Answer 3

按照 user2566092 的说法进行实现：

def f(n):
  return max(fl(n),fh(n))
def fl(n):
  if n>=0:
    return f(n-1)+x["low"][n]
  else:
    return 0
def fh(n):
  if n>=0:
    return f(n-2)+x["high"][n]
  else:
    return 0
x={"low":(30,5,20,25,500),"high":(0,50,70,100,110)}
print f(4)
#650

编辑：如果您想要O(n)的解决方案：

x={"low":(30,5,20,25,500),"high":(0,50,70,100,110)}
flist=[]
fhlist=[]
fllist=[]
for i in range(5):
  if i-1>0:
    fllist.append(flist[i-1]+x["low"][i])
  else:
    fllist.append(x["low"][i])
  if i-2>=0:
    fhlist.append(flist[i-2]+x["high"][i])
  else:
    fhlist.append(x["high"][i])
  flist.append(max(fhlist[i],fllist[i]))
print fllist
print fhlist
print flist
#[30, 5, 70, 125, 650]
#[0, 50, 100, 150, 210]
#[30, 50, 100, 150, 650]

- MaSp