Average Algorithm

[Dieuz]

Hey guys,

I am facing a new problem. I would like Autoit to find several solutions to the Average equation below:

I choose "Average" and "N".

I want Autoit to find the possible values for a,b,c,d,e,f,g,h,i,j.

N= a+b+c+d+e+f+g+h+i+j

Values of N,Average, a,b,c,d,e,f,g,h,i,j are > 0 and Integer.

Anyone mind helping me?

Thanks alot guys!

Edited March 30, 2010 by Dieuz

[Fulano]

Disclaimer: It's been a couple of years since my last math course, so I could be wrong.

This is more of a math problem, and it's not really solvable without a system of equations that would give more information about each of these variables. Without more information there are an almost infinite number of solutions.

[jchd]

That's an easy and small instance of the unbounded knapsack problem.

You can get decently fast results with almost any of the proven algorithms for solving it. Please note that there is no notion of optimality for the solutions. Also it can get more tough if you [very] significantly increase the size of the problem.

Make it:

a + 2*b + 3*c + 4*d + 5*e + 6*f + 7*g + 8*h + 9*i + 10*j = N*average

Depending on N*average there may exist number-theoretic considerations which could make a given instance trivial, due to the fact you use smooth (slowly increasing and even consecutive) integers as weights. But in the case of small size problems, I wouldn't even care as looking for such possibilities could prove way more complex than solving it directly.

Edit: at first I didn't notice your condition that coefficients should not be zero. If you really need that extra condition, you may have to change the presentation a bit because the generic problem traditionnally allows coefficients to be null.

That requires that N*average >= a+b+c+d+e+f+g+h+i+j but if that condition holds, you can always rewrite the problem this way:

B + 2*C + 3*D + 4*E + 5*F + 6*G + 7*H + 8*I + 9*J = N*average - (a + b + c + d + e + f + g + h + i + j)

and solve for {B .. J} allowing zeroes.

Edited March 30, 2010 by jchd

[Fulano]

Ahhh, my math knowledge failed me again, good catch jchd