怪物与你：一个优化难题

问题描述

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.

推荐答案

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