Блог пользователя edgerunner

I need HELP pls
Автор edgerunner, история, 9 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
9 месяцев назад, # |
← 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.

→ Ответить
»
9 месяцев назад, # |
  Проголосовать: нравится 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.

→ Ответить
»
9 месяцев назад, # |
← 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]

→ Ответить
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    thank you, will need time to digest)

    → Ответить
    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Your Welcome

      You 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:
      • 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:
      • 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:
      → Ответить