atlasworld's blog

Help in this dp problem , 19B ,codeforces
By atlasworld, history, 7 years ago, In English

can anyone please explain how this problem will reduce to 0/1 Knapsack problem after increasing each t[i] by 1?

why we are increasing t[i] by 1 ?

Tags #dp
  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Cause when we buy i-th item we will have this item plus t[i] items, in sum we have t[i]+1 item instead t[i]

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    ok ..

    so our number of items increase by t[i]+1 if we but i_th item , but how will we reduce it to knapsack equation , what will be the dp state & base case ?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      U can use my solution to better understand 40091182 There dp[i][j] means minimum cost of j items when we already looked through i items

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

        what does dp[i][j] means in ur code ?

        i can be the item that you are currently processing ?

        what does j refers here ? can you please tell me a bit !

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

          There dp[i][j] means minimum cost of j items when we already looked through i items

          → Reply