electro177's blog

By electro177, history, 2 years ago, In English

I was doing problem towers.I sorted all the blocks according to weight + strength from exchange arguments and then now i did not get idea how to do transitions in dp ,but i saw some code and i thought i should do it by weights from 0 to total weight (but i do not know why) and the transition was

Your code here...

for (auto block : blocks) {
int w = block.w, s = block.s; ll v = block.v;
for (int i = w + s; i >= w; i--) 
dp[i] = max(dp[i], dp[i - w] + v);

Please help me how to take the dp state and also the transitions mainly(i did not understand after thinking a lot) Thank you

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

| Write comment?
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I myself am not that good in DP, but I can share the tips I learnt from various problems and videos.

Before trying to find the state of the DP, I first try to identify if there are any sub problems, that first can be solved so that you can transition into a bigger problem. In the case of the problem that you mentioned, the sub problem would be solving for the answer for the first i blocks. You will get better at identifying sub problems as you solve more problems because till the intermediate stage, dp problems will just be variations of classic dp problems. In your case, the problem is a 0-1 Knapsack problem with no variation.

Now after you identify the sub problem, you need to think of a way to transition from that sub-problem to a bigger problem. Think about how the bigger problem depends on the smaller problem, try to identify any relation. (don't mind the constraints at this stage because once you get a stepping stone, then you can further optimize it) While thinking of transitions, you simultaneously need to think about what information do you need to transition. This information will be the state of your dp.

In my opinion, dp is such a topic that you will only be able to learn through practice and experience.

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

Since you already said that you have ordered all blocks according to $$$W_i + S_i$$$, I won't explain why this is optimal.

I think there is more than one way to solve this DP, but I did it like so...

$$$DP_{i, remainingStrength} = $$$ maximum value you can get by stacking blocks in $$$[i .. n]$$$ while having sum of weights smaller than $$$remainingStrength$$$. You can think of the second state as being the minimum "remaining" strength among all stacked blocks. I assume that the strength of all stacked blocks reduces by $$$W_i$$$ whenever block i is added to the stack. By modelling the DP like this, the transitions are quite straightforward.

$$$DP_{i, remainingStrength} = max( DP_{i + 1, remainingStrength}, V_i + DP_{i + 1, min (remainingStrength - W_i, S_i)} )$$$

It is possible to remove the first state from memory, but it isn't necessary given the constraints of the problem.