The problem was in a long story format but let me simplify it for you :-)
Problem: Some genie has power P. He wants to grant n wishes of the form {xi, yi}. Now to grant i-th wish he needs to have at least power xi and after granting this wish his power becomes P-yi. In this process, his power shouldn't dip below zero. What is the maximum no. of possible wishes he can grant using his power?
Constraints: 1<=n<=100, 1<=P<=30000, 1<=x<=30000, -300<=y<=300
I couldn't solve this problem in test time, I've seen so many problems of this type but I always fail. I would be grateful if someone explains this. Thanks have a good day!
https://mirror.codeforces.com/contest/1203/problem/F2, the exact question, you can refer to the editorial, if its of any help.
cool, I will look at the problem editorial seems interesting to me.
Deleted.
this is just the classical 0-1 knapsack problem but with different statement.
you can learn about it here: wikipedia and geeksforgeeks
I guess in knapsack problem the weight is constant but in this case it changes with each pick up, here yi could increase or decrease the power.
then why don't you take all the positions that have negative y_i and then do knapsack