In front of you there is a treasure containing many gems, soon you realise that they are not as precious as they seem! Infact they are cursed with black magic and bring bad luck with them so you try to minimise the bad luck you get. You have the power to destroy 1 gem in 1 second. You can destroy gems in any order. You are given a 2D array A, where for i'th gem it takes A[i][0] seconds to give A[i][1] units of bad luck.At any instant, only one gem can give you the bad luck, and you can decide the order in which you want to receive the bad luck. Once the receiving of bad luck starts from any gem it cannot be destroyed and it automatically vanishes after giving A[i][1] units of bad luck. Although while receiving bad luck from any gem, you can choose to destroy any other gem which is available in the treasure. There is no time lapse in between receiving of bad lucks from any two gems. As soon as one gem finishes giving bad luck, you have to choose second gem from the treasure to receive the bad luck. Return the maximum amount of bad luck that you can avoid/destroy. Note: Receiving bad luck is a continous process. And at any instant you cannot receive bad luck from more than one gem. If you are recieving bad luck from any gem then you can choose second gem only after A[i][0] seconds.
|A|<2e3
Seems to me a simple knapsack problem.
can u give the logic?
Calculate the cost of two scenarios:
1) Receive bad luck from the current gem (add its bad luck units) and continue with the next gem after the required time (a[idx][0] + 1). This can be done recursively: a[idx][1] + knapsack(cap — a[idx][0] — 1, idx + 1, a).
2) Skip the current gem and move on to the next one: knapsack(cap, idx + 1, a).
Return the minimum cost between these two scenarios, and memoize it in dp[idx][cap].
The required ans = total sum of bad luck — min cost
PS: cap is the remaining time available for destroying gems, idx is the current gem index being considered.
is it correct?
what is the base case
did you get any answer?
I hope it may help :)