1
$\begingroup$

so i have this problem where:

  • I have to accomplish a challenge A with n quests. Each quest gives me:

    1. p points and
    2. 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.

I will put a picture just to make more clear the whole problem: image

Improve this question
$\endgroup$
12
  • $\begingroup$ I don't understand the problem. If the problem is to complete the one challenge that gives M points, well, complete that challenge and you are done. Can you please edit the question to state the problem more clearly? Can you tell us where you encountered this and give a proper citation? Can you follow our general advice on dynamic programming at cs.stackexchange.com/tags/dynamic-programming/info, follow the steps, and edit to show what progress you've made and at what stage you got stuck? Can you find an (exponential-time) recursive algorithm? $\endgroup$
    – D.W. ♦
    Mar 24, 2021 at 17:51
  • $\begingroup$ Well 1 challenge has multiple quests. Each challenge needs M points to be completed. In order to complete a challenge you have to do quests. Quests are like small problems which give you points. Each quest gives you different points and needs a certain time to be completed. The only way you can complete a challenge is to complete enough quests so that you can gather the M points that you need to have in order to finish the challenge. $\endgroup$
    – Chris Costa
    Mar 24, 2021 at 18:37
  • $\begingroup$ Please edit the question to clarify and to answer the questions marked above. Are there multiple challenges? What is meant by "the challenge that needs M points ..."? Does each challenge have a different number of points it needs? If there's only one challenge of that form, why does it matter that there are other challenges? Can you share with us the original source, so we can refer to the original problem statement? $\endgroup$
    – D.W. ♦
    Mar 24, 2021 at 18:38
  • $\begingroup$ Okay so i will try to give it my best explanation. I think that i have explained it good on the question. It is a free translation from Greek so that's why it is messy. Okay, so: 1) I am given 1 challenge. This challenge has certain quests (q1,q2,......,qn). [Challenges and quests are not the same thing, many quests make 1 challenge] 2) Each quest has some points that you get if you complete it 3) Each quest has a time that you need so you can solve it 4) You are only solving quest 5) If you get enough points you have basically completed the challenge $\endgroup$
    – Chris Costa
    Mar 24, 2021 at 18:48
  • $\begingroup$ Please don't explain in the comments. Instead, edit the question to make it clear. We don't want people to have to read the comments to understand what you are asking. Feel free to take your time making an edit to make it clear and so it reads well for someone who encounters this question for the first time. We want to build up an archive of high-quality questions that will be useful to others in the future. $\endgroup$
    – D.W. ♦
    Mar 24, 2021 at 18:50

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.