I am trying to solve this question using recursive dp but i am stucking in between . PLease modify my code to the correct solution so that i have clear picture of base case and states of the dp .
Here is the link to my code
Knapsack 2 Atcoder educational dp contest https://atcoder.jp/contests/dp/tasks/dp_e
Notice that value is small (at most 105105 for all 100100 items), so instead of “what is the most value we can carry with weight W”, you find “what is the least weight you need to carry to get a value of V”.
You can refer to this solution.
I saw you solution sir and my logic as well as concept becomes clear. But most important is that after understanding the concept , you should be able to write the code . I wrote code by myself but getting incorrect ans .
1 Like
I saw you solution sir and my logic as well as concept becomes clear. But most important is that after understanding the concept , you should be able to write the code . I wrote code by myself but getting incorrect ans . Please tell me where i am mistaking . Here is the link to my code https://ide.codingblocks.com/s/320259
Either use 0 based indexing in main() function or you have to make appropriate changes in the knapsack function,because all of that function is written as per 0 based indexing.
PRO TIP: try making the table on pen and paper, things will get more clear.
Still if you find difficulties, I’ll also help help you out with the code.
But do try it once on your own first. Hope this helps 
see this code for reference
In your code,
I’ve made some changes in the input taking in main function, and changed line 35, also used long long int instead of int everywhere to avoid overflow.
you can check it here.
My solution was correct but I was storing INT_MAX in array variable …thats why i was getting incorrect ans .It was not needed to changed the 1-based indexing to 0-based indexing. Btw thank u so much.