Kill the birds from hackerblocks

#1

can u plz tell me how to slove kill the birds from hb its look like knapsack prob but how to deal with probability here??

#2

This problem can be solved by dynammic programming Problem asks you to maximize your chances of winning i.e scoring atleast W points in this case. At each turn, you have two chances to choose from.
So, Lets maintain a state F(idx, pts) where idx denotes the turn which you are on and pts denotes the number of points you have fetched till now. So, overall the state denotes the maximum expected probability you can achieve while you are at idxth turn and having pts points.

F(idx, pts) {

   if ( idx == n ) return (pts >= w)

   //lets take choice #1
  //Now, we either hit the target with prob p1 or miss it with (1-p1)
   double  ans1 = p1*f(idx+1,pts+x) + (1-p1)*f(idx+1,pts)

   //lets take choice #2
  //Now we either hit the target with prob p2 or miss it with (1-p2)
   double ans2 = p2*f(idx+1,pts+y) + (1-p2)*f(idx+1,pts)

   return max(ans1,ans2)
}

my solution : https://ide.codingblocks.com/s/185041

In case of any doubt feel free to ask

and if you got the answer please marks it as resolved