Maximum Value But Limited Neighbors

+2 votes

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: (i) For each j, b[j] is 0 or 1, (ii) Array b has adjacent 1s at most k times, and (iii) sum_{j=1 to n} a[j]*b[j] is maximized. For example, given an array [100, 300, 400, 50] and integer k = 1, the array b can be: [0 1 1 0], which maximizes the sum to be 700. Or, 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.

asked Jun 20 in Dynamic Programming by Baijun Xie AlgoStar (400 points)

1 Answer

+1 vote
 
Best answer

Notation

MVBLN(i,m): Maximum value sum that can be achieved from the array A[1..i], using adjacent 1s at most m times.

Recurrence Relation

MVBLN(i,m) = max{MVBLN(i-1,m), MVBLN(i-1,m-1) + A[i], MVBLN(i-2,m) + A[i]}

Base Case: MVBLN(i,0) can be solved separately, using a separate problem, that we can call maximum value no neighbors.  MVNN(i) = max{MVNN(i-1), MVNN(i-2) + A[i]}. MVNN(0) = 0.  MVNN(1) = a[1].  MVNN(2) = max{a[1], a[2]}.

Optimality

MVBLN(i,m) is either an extension of MVBLN(i-1,m-1) that includes A[i], or extends MVBLN(i-2,m) that includes A[i], or something that uses MVBLN(i-1,m) and just ignores A[i].

answered Jul 18 by Amrinder Arora (38 points)
selected Jul 18 by Baijun Xie
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...