akshayar_01's blog

By akshayar_01, history, 8 days ago, In English
 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by akshayar_01 (previous revision, new revision, compare).

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

This is 0/1 Knapsack with some additional tweak.

If you don't know what is 0/1 Knapsack : https://www.youtube.com/watch?v=U4O3SwDamA4

After you know how to solve for 0/1 Knapsack, read below.

Dp States :

dp[i][j][0] = The maximum energy we can get from first i elements that have a weight of j and number of Blue objects taken is even.

dp[i][j][1] = The maximum energy we can get from first i elements that have a weight of j and number of Blue objects taken is odd.

Transitions : Try to find them out, will be a good problem for you.

Solution Code(With Comments, Only see it you have tried writing Transitions) : https://ideone.com/ltzja3