Given n and 2 arrays a[i] denoting the time taken to eat ith grape and and b[i] denoting the power gained by eating the ith grape repectively. The total time to eat is T minutes. You can eat one grape irrespective of how many minutes it needs in usual time during the Tth minute of consumption. Find the max power that can be obtained in T minutes. N<=3000 T<=3000 1<A[i],b[i]<=3000
sample tc: n=2 T=60 a[i]={10,100} b[i]={10,100} output : 110 explanation: We can eat the 1 grape in first 10 miniutes.Then in the next 10 minute he can eat the second grape . power=10+100=110.
tc:2 n=2 T=60 a[i]={100,100} b[i]={100,100} output : 100 Explanation: Only one grape can be consumed.After that T minutes get over.. plz explain how to solve this question..I think dp would be used here...but i am not sure..
It's looks like 0-1 Knapsack problem:
https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/
I am not sure, since I don't understand the problem (in particular — first example). Would it help if you provide link to actual problem?
Explanation of the Question:- If at the end let's say 5 min left and time reqd to consume the Apple is 100min then we can take that Apple nd this can be done once only.
I have several ideas, but I can't test them because you didn't provide link to the problem :D
One possible solution is to pick grape with highest power and eat it at the end. Now you want to choose from other grapes maximum power in time T-1. You can do that with 0-1 knapsack.
I also was thinking about greedy approach. Sort grapes by value = power / time. Then take grapes with the greatest value until you reach or exceed time T.
The one which is giving maximum profit can have a min time reqd so I don't think this would give correct answer.
I don't think greedy would work here as there might be a possibility where better option would be if we take the grape which is having maximum time nd also giving us maximum power in last minute.
No, this problem is not on codeforces
Can we both agree that taking grape with maximum power at the end of the time (this one grape that exceed time) is correct choice? Then all you need to do is to calculate what is maximum power you can get with other grapes in time T-1. And this problem can be solved by using 0-1 knapsack.
I don't think this would work as there might be a case where we don't need to take the grape in last minute
Counterexample or didn't happend ;-)
You could try a
dp[i][j][k], wherekis either 0 or 1.dp[i][j][0]is just a regular knapsack, whiledp[i][j][1]doesn't take into account the time limit, so if you have X minutes left and a grape with required time T, T > X, you can still use it.