Algorithm for Approximation of the Optimal Solution of the Integer Distribution Problem

I created a possible solution and implementation in C # . Hope this is what you need. It would be nice if someone proves this is right / wrong, but it works and the results look right. Below are the details of the theory. Its complexity is something about O(N!*M^3*Log2(N))

, where N

is the number of variables, and M

is the number of terms of all sums.

By the way, for your example, it gives the following output:

c=3, a=2, d=2, b=1
{a+b=3; b+c=4; c+d=5; a+a+d=6; b=1}
max=6

      

        
        
        
      

    

UPDATE

Algorithm theory.

Suppose the variables are ordered eg. a >= b >= c >= ....

Let's say that the sum of the sums is a bag if all the sums in it are different. All the amounts in the bag can be divided into two groups: the amounts that do not contain the variable a

and the amounts that do. Allows you to call the first group as "Head" and the second as "Tail". Please note that both are bundles because they contain different amounts. We can subtract a

from each sum in the tail to keep all sums different (i.e. the tail is still a bag). Thus, we get two packages without a variable a

.

Likewise, we exclude the variable b

from two Bags and get four Bags. This operation is repeated for each variable until we get the sums with the last variable (say this d

). The smallest value d

is 1.

After that, we can go back to the previous step and include the variable c

in the sums from the tails. Remember that we have many Head-Tail pairs and you need to join them. To do this, add c

to each sum in each tail so that the sums from the tail should be different from the head.

How to calculate c

? The idea is to compute your invalid values ​​and then accept the smallest value that is not invalid and is equal to or greater than d

. Evaluating invalid values ​​is trivial using the HeadSum != TailSum + c

=> condition c != HeadSum - TailSum

. For every combination of tail sum and head sum, we get all invalid values.

By dropping all Head-Tail pairs back and evaluating each variable, we get a solution for the case a >= b >= c >= d

. We then compute the solution for each permutation a >= b >= c >= d

and find the smallest one.

PS It would be great if someone provided a better solution because I believe my algorithm is more of an approximation (but a good approximation) or even better to prove it. Worst of all is the complexity N!

because of the permutations, and I still don't know how to get rid of it.