### edgerunner's blog

By edgerunner, history, 7 weeks 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

 » 7 weeks 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.
•  » » 7 weeks ago, # ^ |   +7 1 4 6, 1 3 6?
•  » » » 7 weeks ago, # ^ |   0 oh then i know only 1 way dp
 » 7 weeks 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.
•  » » 7 weeks ago, # ^ |   0 but choosing from both odd/even indexes maybe optimal: 1,3,6 etc.
•  » » » 7 weeks ago, # ^ |   +1 Then you can't take n/2 element.
•  » » » » 7 weeks ago, # ^ |   0 we must take n/2 elements with min sum, pls reread the description
 » 7 weeks 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]
•  » » 7 weeks ago, # ^ |   0 thank you, will need time to digest)
•  » » » 7 weeks 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) 
•  » » » » 7 weeks ago, # ^ |   0 got it for a 100% now. thank you)