在k个相邻的1秒（最大值限定邻居） [英] At most k adjacent 1s (Maximum Value limited neighbors)

问题描述

在我的算法当然，还有的书，去如下的问题：你将得到一个数组[1..1]的正数和一个整数k你必须产生一个数组b [1。 .N]，使得：对每个j，B [j]为1或0数组b至多K次具有邻近1秒萨姆（一个[j]的* B [j]的）为1所述; = J＆所述。 ; = N最大化。例如，给定的阵列[10，100，300，400，50，4500，200，30，90]，且k = 2的数组b可以是= [1，0，1，1，0，1，1，0 ，1]其中最大的一笔5500

In my algorithms course, there's a question in the book that goes as follows: "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." For example given an array [10, 100, 300, 400, 50, 4500, 200, 30, 90] and k = 2 the array b can be = [1, 0, 1, 1, 0, 1, 1, 0, 1] which maximizes the sum to 5500.

该解决方案采用动态规划法，他们说的递推关系是形式的M（I，J）= MAX（M（I-2，J）+ A [1]中，M（I- 1，J-1）+ A [1]）

The solution uses Dynamic programing when discussing this with some friends they said the recurrence relation is of the form M(i, j) = max(M(i-2, j) + a[i], M(i-1, j-1) + a[i])

有人可以解释为什么这样呢？或者，如果它们具有不同的形式解决这种问题的。我觉得动态编程有点难以把握。 谢谢。

can someone explain why so? or if they have a different form of solving such a problem. I find Dynamic programing a bit hard to grasp. Thank you.

推荐答案

M [I，J]是最大金额从1到i，其中j相邻的1秒

M[i, j] is max sum from 1 to i, with j adjacent 1s

M [I，J]可以计算为3的情况下的最大：

M[i,j] can be computed as the max of 3 situations:

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]的一个= [1]原因是b [1..1]仅具有一个条款b [1] = 1和没有相邻1秒

The recursive rule is the max of the 3 sums above. The end condition is M[1, j]=a[1] because b[1..1] has only one item b[1]=1 and no adjacent 1s.

我们需要的答案是M [N，K]。

The answer we need is M[n, k].

复杂度为O（NK）。

这篇关于在k个相邻的1秒（最大值限定邻居）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！