怪物与你：一个优化难题 [英] Monsters vs you : an optimisation puzzle

问题描述

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.

INPUT : 
B 
N 
K1 G1 
K2 G2 
. 
. 
KN GN
Where

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.

OUTPUT : 
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.

推荐答案

如果您有实施，那么您需要与我们分享，所以我们可以确保我们建议会有所不同。

如果没有这个，我们必须假设这是一个伪装的尝试来完成你的功课！ ：笑：



我们不做你的作业：这是有原因的。它就是为了让你思考你被告知的事情，并试着理解它。它也在那里，以便您的导师可以识别您身体虚弱的区域，并更加关注补救措施。

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.

这篇关于怪物与你：一个优化难题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！