so i have this problem where:
I have to accomplish a challenge A with n quests. Each quest gives me:
- p points and
- needs t time to be done.
The object is to complete the challenge A that needs M points to be completed, in the least possible time.
So let's say A has these following quests:
q1 => p1=20 points, t1=5 minutes
q2 => p2=40 points, t2=20 minutes
q3 => p3=10 points, t3=2 minutes
q4 => p4=30 points, t4=6 minutes
I want to solve this problem for M = 50. Note that you cannot solve challenges, you can only solve quests. If you get enough points with the quests that you have completed, then you can say that you have completed challenge A.
I could solve q2 and q3 in time 22. I will get the 50 points, but it's not the optimal solution since solving q1 and q4 will also give me 50 points in time 11.
I know that this is a knapsack problem but i just can't figure out how i am suppose to store in my table so i can get a result the set of quests that have to be done in order to have the least possible time. I need to find a dynamic programming algorithm which will be able to find the answer. If someone knows how my data structure should look like and how i should store the data inside, generally what idea should i follow in order to solve this problem, i would really appreciate help since i've been stuck and i don't know how to solve it.