myaw's blog

By myaw, history, 4 years ago, In English,

I just solved this problem in uva.onlignejudge 10664 a classical dp problem ( you have n weights and you want to find a way to distribute these weights equally between 2 people ) so you only need a simple dp to find (total sum of weights ) / 2 using given weights .

but what if we decided to shares these weight between k people how to solve that ? do we have to keep track on the chosen weights ??

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved the problem : http://lightoj.com/volume_showproblem.php?problem=1147 The problem is almost similar to your question . Thanks .

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    obviously you didn't read my statement will , i was able to solve that problem for 2 people now i'am asking how we solve it for k people ??

»
4 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

You can do brute-force for O(kn) or dp for O(k^{2}*MAXSUM^{k — 1}).

I dont think it's possible to solve it faster.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you give your dp approach ??

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      dp[i][val1][val2]...[val k -1] is it possible to distribute birst k items, so first have val1, second — val2 and so on. There are k * MAXSUM(k - 1) states and you need O(k) to do step, you simply choose who takes ith item.