5

Every box has at least no balls and at most N balls. Of course the total number of balls in M boxes must equal to N.

For each allocation, I calculated a value based on the allocation: V=f(n_1,n_2,...n_m). I want to find out the maximum of V given N,M and f. I need to store the maximum V and the corresponding allocation results.

Using loops the complexity should be O(N^M), but loop isn't the way to go in this case.

Any hint or suggestion is greatly appreciated. Having few classical DP algorithm at hand but no luck.

Note: f = f1 + f2 + ... f_m, where f(i)'s are polynomials. f(i) only depends on n(i).

2

I do not know what DP algorithms you tried, but here is one which solves your problem in O(M * N²), which is certainly better than O(N^M).

The algorithm works inductively by increasing number of boxes. In each step, you store the maximum of f1+...+f_m, where m is the number of boxes in the particular step (0<=m<=M). For a given m, you solve the problem for every n between 0 and N, and you use the solutions for m-1 boxes to solve the problem for m boxes (also for every n between 0 and N).

For m=1, generate the solutions for 0<=n<=N -> O(N)

For m=2 and each 0<=n<=N, use still "brute force" -> O(N²)

For m=3 and each 0<=n<=N, and 0<=k<=n, calculate f3(k) + max((f1(x1)+f2(x2)), where x1 + x2 = n-k (the maximum term is the result of the step m=2. For each n, keep the maximum value over all k. -> still O(N²), which is the same as O((m-1)*N²)

Now continue that way: each step needs only N*(N+1)/2, thus O(N²), new calculations, and you have M-1 steps in total, so the overall complexity is O(M * N²).

| improve this answer | |
  • What's f3(k)? – Lovnlust May 3 '15 at 15:54
  • @W_ee: see my edit. f3(k) is the value of the polynom f3 when evaluated at the number k. – Doc Brown May 3 '15 at 20:35
  • Few more questions. 1. The last term max((f1+f2)(n-k)) is smaller or equal to the maximum of step m=2 cause n-k has range constraint? 2. Let's say M=3.f1 depends on n(1), f2 depends on n(2), if (f1+f2)(n-k) is the value of polynom f1+f2 when evaluated at the number n-k, then in the end box 3 has k balls and box 1&2 has n-k balls? But what I need is allocation over all boxes. – Lovnlust May 4 '15 at 2:18
  • Sorry @Doc Brown. I don't see how can I use the solutions for m-1 boxes to solve the problem for m boxes. When we add one more box, the total number of balls in previous m-1 boxes may change, so does the allocation for previous m-1 boxes. But the solutions for m-1 boxes only records the allocation result corresponds to the maximum value for m-1 boxes. – Lovnlust May 4 '15 at 2:22
  • @W_ee: assume you have solved the problem for m-1 boxes and every n between 0 and N. Now you are going to solve it for m (and also every n between 0 and N). For this, you check first the case where box m gets 0 balls (thus the first m-1 boxes contain n balls), then where box m gets 1 ball (thus the first m-1 boxes contain n-1 balls), then 2 balls, and so on. – Doc Brown May 4 '15 at 6:00
3

If you need not strictly the global maximum but just a “fairly good” solution, you can approach this kind of problem by an approximation technique known as local search. The idea is that you start with a given solution and try to improve it by making “simple small steps”.

In your case, such a step could be moving one ball from one box to another. Here is then a simplistic local search algorithm:

  • amax ← ⊥
  • fmax ← –1
  • Repeat k times:
    • Generate a random allocation a ← (n1, …, nm)
    • While you can find i and j such that ni > 0, nj < N and moving one ball from box i to box j increases f(a):
      • Set a ← (n1, …, ni – 1, …, nj + 1, … nm)
    • If f(a) > fmax:
      • amaxa
      • fmaxf(a)
  • Output the best allocation amax found

If you only repeat the main loop once (k = 1), you'll get the local maximum from a random starting point. This will often not be a globally good solution. By repeating the local search a few times from different random starting points and finally taking the best local maximum, you increase your chances to reach something closer to the global maximum.

If you know more about your f, you might be able to design a better “small step” than simply moving one ball into another box.

The kind of algorithm like local search with multiple random restarts is known as a meta heuristic since it is applicable to a large number of problems without knowing much about them. (This particular form is also sometimes referred to as the hill climber algorithm.) If you search for meta heuristics, you'll find a wealth of approaches to choose from.

| improve this answer | |
  • So such algorithms outputs fairly good result given k is enough large? Given N balls and M boxes, total combination is C(N+M-1,M). Thus K_max = C(N+M-1,M)? – Lovnlust May 3 '15 at 14:44
  • How large k should be mostly depends on f. If it is fairly smooth, then a small number will suffice. If by C (n, k) in your comment you mean n choose k, then no, a much smaller k should do. I'd simply try a few out. Hint: what is the maximum number of maxima your f can have? – 5gon12eder May 3 '15 at 14:48
  • Yea that means n choose k. Even f is relatively smooth and only has few maximas, how can a small k guarantee it can search all maximas? – Lovnlust May 3 '15 at 14:51
  • It can't. It remains an approximation heuristic. If anything but the global maximum is unacceptable, then this is not a good approach. But often times, getting a good solution with high probability fast is good enough, even if it's not the optimal one. It depends on your problem domain. – 5gon12eder May 3 '15 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.