python - 确定在最大利润难题中被抢的房屋

我正在尝试“智能小偷”问题，我们在该问题中列出了邻近房屋的价格，目的是使利润最大化。一个限制是，一旦房屋被抢劫，在其左侧或右侧的房屋就不能被抢劫。我设法用以下代码找出了赃物的最大值：

def max_theft(house_val, n):
    if n == 0:
        return 0
    if n == 1:
        return house_val[0]
    if n == 2:
        return max(house_val[0], house_val[1])


    max_theft_val = [0]*n


    max_theft_val[0] = house_val[0]
    max_theft_val[1] = max(house_val[0], house_val[1])


    for i in range(2, n):
        max_theft_val[i] = max(house_val[i]+max_theft_val[i-2],   max_theft_val[i-1])

    return max_theft_val

但是，问题的下一部分将是确定哪些房屋可以弥补这一总和。有没有办法解决这个问题？

最佳答案

这是一种方法。注意何时选择房屋并将其添加到列表中。如果下一个选择的房子少于前面的两个房子，则替换列表中的最后一个房子；否则，添加它。

JavaScript代码（对不起，在智能手机上，但这应该很容易适应）：

function max_theft(house_val, n){
  if (n == 0)
    return 0
  if (n == 1)
    return house_val[0]
  if (n == 2)
    return Math.max(house_val[0], house_val[1])

  let max_theft_val = new Array(n).fill(0)

  let chosen = [house_val[0]]

  function add_house(i){
    if (i - chosen[ chosen.length-1 ] < 2)
      chosen[ chosen.length-1 ] = i
    else
      chosen.push(i)
  }

  max_theft_val[0] = house_val[0]

  let a = house_val[0]
  let b = house_val[1]

  if (a > b){
    console.log(`Choosing house 0`)
    max_theft_val[1] = a
    add_house(0)

  } else {
    console.log(`Choosing house 1`)
    max_theft_val[1] = b
    add_house(1)
  }

  for (let i=2; i<n; i++){
    let a = house_val[i] + max_theft_val[i-2]
    let b = max_theft_val[i-1]

    if (a > b){
      console.log(`Choosing house ${i}`)
      max_theft_val[i] = a
      add_house(i)

    } else {
      console.log(`Choosing prev best ${i-1}`)
      max_theft_val[i] = b
    }
  }

  console.log(`Chosen ${chosen}`)
  return max_theft_val[n-1]
}

var arr = [1,4,3,40,50]

console.log(JSON.stringify(arr))
console.log(max_theft(arr, arr.length))