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

SPOJ — LPPP Lov-e Pap Pap-e Polti
Автор abhishekg, 10 лет назад, По-английски

some one please help me how to approach http://www.spoj.com/problems/LPPP problem. I am not getting any idea how to solve this problem. Although i have read about how to divide an array into two sets of equal sum using dynamic programming but not able to get this one.

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

»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

It's easy to imagine recursive DP:

bool DP(int a, int b, int c, int coinNumber)
{
   if (coinNumber == n) return a == b && b == c;
   return DP(a + coinValue[coinNumber], b, c, coinNumber + 1) ||
       DP(a, b + coinValue[coinNumber], c, coinNumber + 1) ||
       DP(a, b, c + coinValue[coinNumber], coinNumber + 1) ||
}

Where a, b and c — amount of money for three brothers.
Now you should transform recursive DP into iterative.

dp[0][0][0] = true;
for (int coinNumber = 0; coinNumber < n; ++coinNumber)
{
   dpNew = AddCoinToDPTable(dp, coinValue[coinNumber]);
   dp = dpNew;
}

Note you don't need to store value c, because a+b+c is constant and equals to coinValue[0]+... +coinValue[coinNumber]. So you need DP table dp[50 * 50 / 3][50 * 50 / 3]

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    @Alias thanks

    Accepted now :)

    but can you tell me how to solve this problem using bottom up approach as i don't get how to solve

    this problem using bottom up approach , i solve this problem using memoizaton...

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится 
      mat AddCoinToTable(const mat& d, int coinValue)
{
    mat res = d;
    FOR(a, N)
        FOR(b, N)
            if (d[a][b])
            {
                if (a + coinValue < N)
                    res[a + coinValue][b] = 1;
                if (b + coinValue < N)
                    res[a][b + coinValue] = 1;
            }
    return res;
}

bool CanDivide(const vi& coinValues)
{
    mat dp(N, vector<char>(N, 0));
    dp[0][0] = 1;
    FOR(coinNumber, coinValues.size())
    {
       mat dpNew = AddCoinToTable(dp, coinValues[coinNumber]);
       dp = dpNew;
    }

    int sum = 0;
    FOR(i, coinValues.size())
        sum += coinValues[i];

    return sum % 3 == 0 && dp[sum / 3][sum / 3] != 0;
}
      → Ответить