Distributing N items with different values into groups which are only valid if sum of items in the group is D

Question

I have an array of N integers each having different values between 5 and 20. I want to form as many groups as possible from them such that their total is an integer value D.

There is no limit on how many groups formed, how many numbers a group has or that every element of the array has to be used; we must create as many groups as possible and only one group is enough.

Here are my limits:

5 <= V: Value of an item <= 20
5 <= N: Number of elements <= 10000
20 <= D: Sum of numbers of a single group <= 2000

Examples

A:
Array:{5,7,7,6,6,8,8,10,11,12}
D:40
One of the accepted solution:
[[5,7,8,8,12], [7,6,6,10,11]]

B:
Array:{5,6,6,7,7,10}
D:20
One of the accepted solution:
[[6,7,7]]

The suggested algorithm preferably should be in psicocode or C-based languages,Java or Phyton. If the accepted answer is not in Java, It will be ported into Java and shared here after a solution is accepted.

Thanks.

EDIT: It seems regardless of chosen method, it will take a lot of time to compute if N is very large number, I will try to limit maximum of N to 50-100 times for now then test for larger cases.

EDIT2: A lot of great solutions, it is going to take me a while to check it though.

Answer 1

I will post a partial solution, that, however, I believe would help you in much of your cases. My suggestion is that you use this in combination of solution approximation for too big problems (which I assume should be relatively rare - are all MMORPG players facing 10000 numbers?).

First, lets convert your data set a bit, replacing the number set, with a map counting the occurences of each number:

{6,7,8,5,6,9,11,6,5,5,5} -> {5 => 4, 6 => 3, 7 => 1, 8 => 1, 9 => 1, 11 => 1} Java solution for that (above => actually spares me to write an array with 20 values, most of which are zero. Above consider that numberMap[5] = 4 etc.)

int [] numberMap = new int[21];
for (Integer number : numbers) {
   numberMap[number]++;
}

In order to continue my solution I would need functions that encode and decode subgroups of the entire number set:

int [] encode(int [] subgroup) {
    long result = 0;
    for (int i = 0; i <= 20; i++) {
        if (i > 0) {
           result *= numberMap[i - 1];
        }
        result += subgroup[i];
    }
    return result;
}

int [] decode(long code) {
    int []result = new int[21];
    for (int i = 20; i >= 0; i++) {
       result[i] = code % numberMap[i];
       code /= numberMap;
    }
    return result
}

Now, lets find all subgroups that will give you amount G, using recursion

List<Long> subgroupsSumG = new ArrayList<Long>();

recursion(5, new int[21], 0);

void recursion(int currentIndex, int [] subgroup, int sum) {
  if (currentIndex == 21) {
     if (sum == G) {
        subgroupSumG.add(encode(subgroup));
     }
     return;
  }
  if (sum > G) {
     return;
  }
  for (int i = 0; i <= numberMap[currentIndex]; i++) {
     subgroup[currentIndex] = i;
     recursion(currentIndex + 1, subgroup, sum + i * currentIndex);
  }
}

Perfect, so now we know which subgroups can form a single group with sum G. How should we find how many such subgroups can we obtain at maximum? This now turns to a knapsack problem with items having multiple dimensions.

long maximumGroupCode = encode(numberMap);
int [] optimalNumberOfGroups = new int[maximumGroupCode];
int maximumNumberOfGroups = 0;
for (long i = 0; i < maximumGroupCode; i++) {
   if (i != 0 && optimalNumberOfGroups[i] == 0) {
     continue;
   }
   int [] decodedGroup = decode(i);
   group_for: for (Long subgroupCode : subgroupsSumG) {
       int [] subgroup = decode(subgroupCode);
       for (int j = 5; j <= 20; j++) {
          if (numberMap[j] < decodedGroup[j] + subgroup[j]) {
              continue group_for;
          }
       }
       long neighbouringGroupCode = subgroupCode + i;
       optimalNumberOfGroups[neighbouringGroupCode] = Math.max(optimalNumberOfGroups[neighbouringGroupCode], optimalNumberOfGroups[i] + 1);
       maximumNumberOfGroups = Math.max(maximumNumberOfGroups, optimalNumberOfGroups[neighbouringGroupCode]);
    }
}

Perfect, so now your answer is in maximumNumberOfGroups variable. This code will get you the most optimal solution always, when it can complete its work. This would happen when:

• maximumGroupCode * subgroupsSumG.size() * 16 is approximately smaller than 10^ 10
• maximumGroupCode is smaller than 10 ^ 8 (for memory reasons).

Please make sure you calculate maximumGroupCode before running even the first program framgent, as it can take infinite amount of time if this number turns to be very large. And btw keep in mind that even long might be just too small to hold the maximumGroupCode value. Maybe BigInteger should be used for the initial calculation.

Answer 2

Think this is NP-complete problem (reduction to subset-sum problem). A simple solution is this:

1. Iterate through each number
2. If number is greater than D discard and go to next number in list
3. if number if equal to D create a new group and add this number, continue to next number in list
4. if number is less that D a. if there is an active group whose current sum plus this number is equal or less than D add this number to that group and update that group's current sum value b. else create a new group add this numner and set the group's sum value to this number
5. continue untill all numbers in list are traversed
6. Get all active groups whose current sum value is D

note: you must maintain a list of active groups and their current sum value.

The above algorithm will provide a solution in linear time, but not necessarily the optimal solution (see NP-complete above)

update

One can optimise the above algorithm with local-search techniques that can make it find optimal solution more frequently, but still not necessarily always optimal solution in polynomial time. Local search would be placed in step 4. in the above algorithm.

update2

note that the problem has a strong dependence on the actual data (and not just their size). For example for data with all ones (values of 1), the problem is polynomial.

update3

An alternative approach (which might be slightly faster than full exhaustive search) is to pre-compute the partitions of number D that include the range of numbers you are interested in. Then traverse the list and check if the current number is part of any of the (pre-computed) partitions of D. This will provide an exact optimal solution. But computing partitions is not polynomial in general.

Answer 3

The backtracking is the solution you are looking to.

Hint : To your array Array:{5,7,7,6,6,8,8,10,11,12} you can create array of true/false or 0/1 array of same size.

Array :{5,7,7,6,6,8,8,10,11,12}
Array2:{0,0,0,0,0,0,0,0, 0, 0}

The Array2 represents the actual group. 0 means it does not belong there, 1 means it does. If you want iterate through all solutions, you can handle it as increasing binary number by 1, in this case you get

0000000000
0000000001
0000000010
0000000011
0000000100
0000000101
....
1111111111

So for example, if you have this

Array :{5,7,7,6,6,8,8,10,11,12}
Array2:{1,0,0,0,1,0,0,1, 0, 0}

The subgroup is 5+6+10=21 (you just write method which is able to count it)

For iterating through all solutions you can use backtracking or just implement "increase binary number by one"

Remember also that this is NPC problem, which means the complexity is O(2^n). In real-life it means on personal computer, you can get solution in reasonable time only for array size of 30 or less.

For array size of 40+ it can takes hours or more.

---

However in real-life scenarious it depends a lot on the input data. If one solution is enough and you get data which are rich on solutions, you can get in average result in reasonable time.

For example you can try 2^30 possibilities and if you dont find solution, you can say "cant find solution for this data" or "the solution for this data probably does not exist" or you can use heuristic which can return solution which is not "perfect" but is "close".