Click here to Skip to main content
15,795,789 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
You are attacked by a set of N monsters in a game. You have to design an algorithm to calculate the maximum number of these you could kill, adhering to the constraints below.

You begin with B units of initial energy.
To kill a monster n (1<=n<=N), you need to spend Kn units of energy out of your reserve. After it is killed, you gain Gn units of energy in return.
At any point, if you do not have sufficient energy left to attack any of the remaining monsters, you stop at that point.

K1 G1 
K2 G2 

B = initial energy you being with(B<100)
N = total number of monsters (N<10000) followed by N lines in the form
Kn Gn = Kn is energy needed to kill monster n(1<=n<=N) and Gn is energy gained after killing monster n(1<=n<=N) These N lines for the K and G values are not sorted in anyway, i.e neither on ASC/DESC order of K, nor on G.

M = maximum number of monsters that can be killed

Provide a Java implementation of the method below (any other language or pseudocode also works)

public static int maxMonsters(int B, int [][] KG) {
  int M = 0;
  //KG is guaranteed to be of length N, KG[n][0] KG[n][1] are Kn and Gn for monster n
  //your implementation goes here
  return M;

What I have tried:

I have my implementation, which I believe to be working well! Intend to see how others tackle/approach the problem and hence posting.
Updated 17-Oct-17 6:09am

1 solution

If you have an implementation, then you would need to share it with us, so we can be sure that we we suggest would be different.
Without that, we have to assume this is a thinly-disguised attempt to get your homework done! :laugh:

And we do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.
Share this answer

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900