### edgerunner's blog

By edgerunner, history, 2 months ago,

How to choose n/2 (n is even) elements from the array such that their sum is minimum and no two elements are adjacent to each other: [4, 2, 1, 1] 1 + 2 = 3 [3, 3, 3, 0, 4, 0] 3 + 0 + 0 = 3 [2, 0, 11, 2, 0, 2] 0 + 2 + 2 = 4

can we do it greedy? (no dp pls)

• -14

 » 2 months ago, # | ← Rev. 2 →   -10 we must choose n/2 element so choose index 1,3,5 or 2,4,6 in case of lenght six and minimum of both is answer.
•  » » 2 months ago, # ^ |   +7 1 4 6, 1 3 6?
•  » » » 2 months ago, # ^ |   0 oh then i know only 1 way dp
 » 2 months ago, # |   0 You have to choose all odd indexes or all even indexes so just test the sum of these two and see which one is minimum.
•  » » 2 months ago, # ^ |   0 but choosing from both odd/even indexes maybe optimal: 1,3,6 etc.
•  » » » 2 months ago, # ^ |   +1 Then you can't take n/2 element.
•  » » » » 2 months ago, # ^ |   0 we must take n/2 elements with min sum, pls reread the description
 » 2 months ago, # | ← Rev. 7 →   0 Initialize 2 prev elements (podd=0,peven=0) and 2 cur elements (codd=0,ceven=0) Let's say the array is 1-indexed, then:if the index is odd then: codd=a[i]+podd;if the index is even then: {ceven=a[i]+min(podd,peven); podd=codd; peven=ceven;}And Final answer will be: min(codd,ceven)This will work because we have to take n/2 elements.[PS: Although this is just space optimized O(1) DP, but the thought process is mostly greedy and easier to understand]
•  » » 2 months ago, # ^ |   0 thank you, will need time to digest)
•  » » » 2 months ago, # ^ |   0 Your WelcomeYou just have to think along the lines: Each odd-even index pair (not even-odd only odd-even) will have exactly ceil(index/2.0) number of elements, not more not less because if it contains more then there will definitely be some elements before them that are adjacent, if it contains less then you can't make n/2 elements from the remaining pair. Example:Index :: No. of Elements it should contain :: [Odd-Even Index pair] 1 :: 1 1 2 :: 1 :: [1-2] 1 2 3 :: 2 1 2 3 4 :: 2 [3-4] and so on... [NOTE: and as you can see this will ensure that n element will have n/2 elements]  the odd index will/can take only from the previous odd index from the previous odd-even pair because if it takes from the previous even then it will be adjacent to it. Example:Index: 1 2 3 4 5 6 1 <-- 3 (Index 3 will take sum from Index 1) 3 <-- 5 (Index 5 will take sum from Index 3)  the even index can take from both previous odd-even index pair (NOTE: previous odd-even pair, not the previous odd or even index otherwise just the previous odd index will be adjacent) Example:Index: 1 2 3 4 5 6 1,2 <-- 4 (Index 4 will take min sum from Index 1 or 2) 3,4 <-- 6 (Index 6 will take min sum from Index 3 or 4) [NOTE: and as you can see that the cur index is not adjacent from prev indexes so it will work) 
•  » » » » 2 months ago, # ^ |   0 got it for a 100% now. thank you)