flyingfist's blog

Do anyone knows how to solve this dp problem?
By flyingfist, history, 10 hours ago, In English

This is a modified 0/1 knapsack problem. The first line contains n, the number of array elements. The next n lines contain the array elements. There are three things given for each element. 1) Type 2) Weight 3) Value and W which is the maximum limit of total weight. So, here we have to maximize the total value, by taking each type of element atmost one time. The constraints are 1<=W,Type,Weight,Value<= 5000. How to solve this problem? What would be the states?

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

»
9 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Table: Dp[count of different types][W]

Transitions: dp[i+1][j]=max(dp[i][j], dp[i+1][j])

dp[i+1][j+WEIGHT_k]=max(dp[i][j]+VALUE_k, dp[i+1][j+WEIGHT_k]) where WEIGHT_k is weight of kth item and VALUE_k is value of kth item, but look only at items that have type==i

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

    But here three things are changing: type, weight used and index. I am not able to understand how are you managing that. Can you elaborate a little?

    → Reply
    • »
      »
      »
      6 hours ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      Let's see this from the forward direction.

      Imagine that dp[i][j] is telling you "The optimal value if I am only using the first $$$i$$$ types of items, and my knapsack weighs exactly $$$j$$$"

      Now let's think about state. Naturally from state [i][j] you consider the next type of items which is type $$$(i+1)$$$. Well, for every $$$k$$$ such that $$$TYPE_k=i+1$$$, consider what state you end up in, if you add it to your current state. Once you add it, you cannot use anything else with type $$$i+1$$$, and your weight increases with $$$WEIGHT_k$$$. So there is a transition from $$$(i, j)$$$ to $$$(i+1, j+WEIGHT_k)$$$ with value $$$VALUE_k$$$. What about if you decide to not pick anything at all from type $$$i+1$$$? Well then it's just a transition from $$$(i, j)$$$ to $$$(i + 1, j)$$$ with a value of 0.

      Now you can use this directly to write a recursive implementation with memoization, or you can inverse the transitions to get the DP described by the original comment.

      You have $$$O(MAXTYPE*W)$$$ different states. Naively it seems like each might take up to $$$O(N)$$$, but a more careful inspection shows that for any fixed $$$j$$$ in the second dimension, the total number of items you'll consider across all possible $$$i$$$'s is $$$O(N)$$$ since each item is of exactly one type, so computation actually amortizes to $$$O(N*W)$$$, so $$$O((MAXTYPE+N)*W)$$$ time complexity and $$$O(MAXTYPE*W)$$$ space complexity, both comfortably work for 5000.

      P.S.

      Since $$$MAXTYPE \leq N$$$ (otherwise you can compress the types initially), it's easier to think of it as time and space complexity as $$$O(N*W)$$$

      → Reply