Problem E knapsack 2

#1

Instead of just iterating over a sample of values from 1 to 1 e 5 for “Value”;
Can’t we just apply the binary search for “Value” from 1 to 1 e 5?

#2

Here’s my implementation which is getting WA: https://ide.codingblocks.com/s/294445

#3

hello @Rhinorox
pls explain ur binary search logic

#4

in tutorial, sir is using brute force on “values” from 2 to 1e5. But in that place i want to use binary search

#5

i know u r applying binary serach on values.
i m asking ur logic.
how u r checking whether particular value is possible or not?

#6

Please go through my code for once, i’ll try to explain what i did: ----> (recurrence fn) = for given “N” and “V” find min. weight “W” . (Our Problem) = We don’t know the value “V”, therefore we apply binary search in monotonic search spaces. (Application) = In the binary search fn. we turn the interval as True if the weight <= W and mark that value “V” as ans and proceed further while marking that interval as False if weight > W

#7

yeah logically ur approach is correct.
but i think implementation is creating some issue.
because we have stored -1 ,INT_MAX in some part of array which distort the monotonic property.

[- 1,0,x ,INT_MAX,-1,y,z…]
our array will have something like this configuration .

brute force willl work.iterate from last and find first value that is not INT_MAX,-1

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.