最多k个相邻的1s（最大值限制邻居）
At most k adjacent 1s (Maximum Value limited neighbors)
在我的算法课程中，书中有一个问题如下："You are given an array a[1..n] of positive numbers and an integer k. You have to produce an array b[1..n], such that: for each j, b[j] is either 1 or 0. Array b has adjacent 1s at most K times. Sum(a[j]*b[j]) for 1 <= j <= n is maximized." 例如给定一个数组 [10, 100, 300, 400, 50, 4500, 200, 30, 90]并且 k = 2 数组 b 可以是 = [1, 0, 1, 1, 0, 1, 1, 0, 1] 将总和最大化为 5500。
解决方案在与一些朋友讨论时使用动态规划他们说递归关系的形式为 M(i, j) = max(M(i-2, j) + a[i], M( i-1, j-1) + a[i])
有人可以解释为什么会这样吗？或者他们是否有解决此类问题的不同形式。我发现动态规划有点难以掌握。
谢谢你。
M[i, j]是从1到i的最大和，j相邻的1s
M[i,j] 可以计算为 3 种情况的最大值：
b[i]=0 => S=M[i-1, j] // a[i] not added to sum, b[1..i-1] has same number of adjacent 1s (j) as b[1..i] because b[i] is zero
b[i]=1 and b[i-1]=0 => S=M[i-2, j]+a[i] // a[i] added to sum, b[1..i-2] has same number of adjacencent 1s, because b[i-1] is zero
b[i]=1 and b[i-1]=1 => S=M[i-1, j-1]+a[i] // a[i] added to sum, since b[i] and b[i-1] are both 1, they count as adjacent 1s, so b[1..i-1] contains only j-1 adjacent 1s
递归规则是上面3个和的最大值。
结束条件为 M[1, j]=a[1] 因为 b[1..1] 只有一项 b[1]=1 且没有相邻的 1s.
我们需要的答案是M[n, k]。
复杂度为 O(nk)。
在我的算法课程中，书中有一个问题如下："You are given an array a[1..n] of positive numbers and an integer k. You have to produce an array b[1..n], such that: for each j, b[j] is either 1 or 0. Array b has adjacent 1s at most K times. Sum(a[j]*b[j]) for 1 <= j <= n is maximized." 例如给定一个数组 [10, 100, 300, 400, 50, 4500, 200, 30, 90]并且 k = 2 数组 b 可以是 = [1, 0, 1, 1, 0, 1, 1, 0, 1] 将总和最大化为 5500。
解决方案在与一些朋友讨论时使用动态规划他们说递归关系的形式为 M(i, j) = max(M(i-2, j) + a[i], M( i-1, j-1) + a[i])
有人可以解释为什么会这样吗？或者他们是否有解决此类问题的不同形式。我发现动态规划有点难以掌握。 谢谢你。
M[i, j]是从1到i的最大和，j相邻的1s
M[i,j] 可以计算为 3 种情况的最大值：
b[i]=0 => S=M[i-1, j] // a[i] not added to sum, b[1..i-1] has same number of adjacent 1s (j) as b[1..i] because b[i] is zero
b[i]=1 and b[i-1]=0 => S=M[i-2, j]+a[i] // a[i] added to sum, b[1..i-2] has same number of adjacencent 1s, because b[i-1] is zero
b[i]=1 and b[i-1]=1 => S=M[i-1, j-1]+a[i] // a[i] added to sum, since b[i] and b[i-1] are both 1, they count as adjacent 1s, so b[1..i-1] contains only j-1 adjacent 1s
递归规则是上面3个和的最大值。 结束条件为 M[1, j]=a[1] 因为 b[1..1] 只有一项 b[1]=1 且没有相邻的 1s.
我们需要的答案是M[n, k]。
复杂度为 O(nk)。