Solving a discrete optimization problem
Complexity

Your problem is NP-hard.  Therefore, you should not expect any efficient algorithm that will always find the optimal solution.

In particular, your problem is a generalization of the knapsack problem.  Suppose we insist that $f_i(5)=f_i(6)=\cdots=f_i(4999)=0$ for all $i$ (but $f_i(5000)$ can be any positive integer), and the same for the $g_i$.  Then the problem becomes exactly the knapsack problem.  In particular, the knapsack problem is a special case of your problem, which means your problem is at least as hard as the knapsack problem, as any algorithm for your problem could also be used to solve the knapsack problem.  Moreover, the knapsack problem is NP-hard, so your problem is too.

Therefore, you're going to have to make some compromises.  You could look for heuristics that produce the optimal solution and sometimes run fast, but in the worst case might take exponential time.  Or, you could look for heuristics that produce an approximate solution (not optimal, but hopefully close to it).  I'll outline several approaches.

Exact solutions

Suppose you want the exact optimum solution.  Then I know of two reasonable approaches, depending on how large $B$ is.

If $B$ is small, you can adapt the standard dynamic programming algorithm for the knapsack problem to this situation.  The running time will be roughly proportional to $B$, so if $B$ is not too large, this is reasonable, but if $B$ is a 100-bit integer, this is completely infeasible.

Alternatively, you can use integer linear programming.  Introduce zero-or-one variables $v_{i,k}$, with the intended meaning that $v_{i,k}=1$ means that you've set $x_i$ to $k$.  Add constraints to ensure that $x_i$ is set to  a single value ($v_{i,5} + \dots + v_{i,5000}=1$) and that $g_1(x_1)+\dots+g_n(x_n)\le B$ (namely, $\sum_{i,k} v_{i,k} g_i(k) \le B$), and then maximize the objective function $\sum_{i,k} v_{i,k} f_i(k)$.  Feed this to an off-the-shelf ILP solver, and it might find a solution for you, if you are lucky and the size of the problem is not too large.

Approximate solutions

If you're willing to accept an approximate solution that isn't necessarily optimal but should be close to optimal, there are several possible approaches.

One approach is to create the ILP problem above, run the ILP solver for a limited amount of time, then stop the solver and ask it to give you the best solution it has found so far.  Many ILP solvers have the ability to do that.

Another approach is to round to a limited precision.  Pick a constant $c&gt;1$, and replace each $g_i(x)$ with $\lfloor g_i(x)/c \rfloor$ and replace $B$ with $\lfloor B/c \rfloor$.  In other words, divide all the $g$'s and $B$ by $c$, and then round to an integer.  Now solve the resulting problem.  This is an instance of your problem, but with smaller numbers and a smaller $B$, so you can now try to find an exact solution to this smaller problem -- for instance, using dynamic programming.  The optimal solution to this smaller problem will correspond to a close-to-optimal solution to the original problem.  You can tune the value of $c$: the larger $c$ is, the more efficient this will be, but the worse the quality of the solution.

There may be other methods.  You could study the literature on the knapsack problem to see what techniques have been considered there and see  how to adapt them to your situation.  But the above is probably a pretty good starting point.