Блог пользователя edem.kwadzo

dp solution for Timus 1005
Автор edem.kwadzo, 13 лет назад, По-английски

Hi Guys,
can anyone help me solve this problem using DP ? is that even possible ?

http://acm.timus.ru/problem.aspx?space=1&num=1005

So far only the brute force (generate all permutations) approach seems to be working.

Many thanks

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Use bit-masks. Take a integer number and look at its bits. If i-bit is 1, then we put stone i+1 in first pile, else in second pile. You need check all numbers between 0 and 2^N - 1 (all possible variants of ones).
It's not DP, but it's fast brut force O (N * 2^N). Also this task can be solved by time O (N * 2^(N/2)) with method meet-in-middle.

→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For dp solution you can use idea of Knapsack problem.

dp[i][j] = true iff using some of i first stones we can get the pile of weight j.

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    In this case, we must open the matrix dp[20][2000000]. This is approximately 40 mb, but we have only 16 mb memory limit
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      No. We don't need to store all 20 lines. We need only 2 lines for calculate dp.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Explain please
        → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

          Look. Let f[i][j]=1 if using some of i first stones we can get the pile of weight j. 

          Then f[i][j]=f[i-1][j] | f[i-1][j-a[i]]; 

          So we need only f[i-1][] to calculate f[i][].

          UPD. We need only 1 line:
          f[0]=1;
          for (int i=1;i<=n;i++) for (int j=m;j>=a[i];j--) f[j]|=f[j-a[i]];
          → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Do not listen to Tranvick =) You need to store 1 line only! - this is only 2 Mb of memory, or 250Kb at all if you use bit operations! So, the problem could be solved by DP even in Pascal!
          → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
This is classic problem, for the dynamical programming with using bimasks. A bit more difficult task when you have 34 stones
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Тhis is a classic NP-complete problem. It is not about the dynamic programming.
→ Ответить