There is a list / array of arbitrary length with integer values. It is necessary to make up from the elements the minimum number of groups in which the sum of the numbers is not greater than the specified value. There is a written algorithm that sorts and forms data groups, but it is rather cumbersome and can work slowly in case of a large amount of data. Does it make sense to decide to use an artificial neural network? Is it possible to train it, if the input data and the maximum sum of numbers in the group can be any?

Example:
Input data:
List of numbers: [6, 1, 6, 2, 4, 3, 1, 2, 2, 3, 2].
Maximum group amount: 10.
The task: to form the minimum number of groups, all groups should be as complete as possible, except for one (minimum balance).
The correct answer is: [1, 1, 2, 6], [2, 2, 6], [3, 3, 4], [2]
Solution: The sum of the numbers in the list is 32. Accordingly, the minimum number of groups is 4; minimum balance - 2; There are 3 groups of numbers, where the sum of the numbers is 10. The problem is that there can be a lot of such numbers and not everything can be perfectly decomposed into groups.
I solved the task without any programming patterns. I am just interested in the possibility and expediency of using ANNs or something similar for a better solution of the problem.

  • How can a neural network help here? - Grundy
  • @Grundy clustering same? - Qwertiy ♦
  • 6
    I suspect that in the presence of accurate algorithms, neural networks in general should not be used. - Qwertiy ♦
  • @ Qwertiy ♦, thanks for the opinion. As I understand it, the main problem of cluster analysis will be an indefinite number of classes-groups of numbers. The architecture of such a network will be extremely complex. - Alex Ross
  • 2
    A neural network is only a sequence of convolutions, that is, weighted sums (in addition, with fractional numbers). So, I think it makes no sense. - ߊߚߤߘ

1 answer 1

The considered problem is a generalization of the well-known knapsack problem , for which the ANN is usually not used to solve.

At the same time, it is possible to recommend "greedy" strategies that are not used in the EP, in which the filling of arrays is searched in descending order of elements.

Implementation option (C #):

public static void Move(ref int[] from, ref int[] to, int index) { int lenfrom = from.Length, lento = to.Length; Array.Resize(ref to, lento + 1); to[lento] = from[index]; for (int i = index; i < lenfrom - 1; i++) from[i] = from[i + 1]; Array.Resize(ref from, lenfrom - 1); } public static void ArShow(string txt, int[] ardesc, int[] res) { Console.Write(txt + "\nlast group: "); foreach (int val in res) { Console.Write(" " + val); } Console.Write("\ndata array: "); foreach (int val in ardesc) Console.Write(" " + val); Console.WriteLine(); } public static void Knapsack(int sum, ref int[] ardesc, ref int[] res) { int ind = 0, sres = res.Sum(), arlen = ardesc.Length, reslen = res.Length; int[] newdesc, newres; Array.Copy(ardesc, newdesc = new int[arlen], arlen); Array.Copy(res, newres = new int[reslen], reslen); foreach (int value in ardesc) { if (sum == sres) break; if (sum >= sres + value) { Move(ref newdesc, ref newres, ind); Knapsack(sum, ref newdesc, ref newres); break; } ind++; } ardesc = newdesc; res = newres; } static void Main(string[] args) { int[] arrdesc, arr = new int[] { 6, 1, 6, 2, 4, 3, 1, 2, 2, 3, 2 }; int rquant, arrlen = arr.Length, sum = 10; int[][] result = new int[0][]; Array.Copy(arr, arrdesc = new int[arrlen], arrlen); Array.Sort(arrdesc); arrdesc = arrdesc.AsEnumerable().Reverse().ToArray(); Console.Write("\nsum = {0}\nissue array: ", sum); foreach (int val in arr) Console.Write(" " + val); Console.WriteLine("\n\n***result.Length = " + result.Length); Console.Write("sorted array: "); foreach (int val in arrdesc) Console.Write(" " + val); Console.WriteLine(); while (arrdesc.Length > 0) { rquant = result.Length; Array.Resize(ref result, rquant + 1); result[rquant] = new int[0]; Knapsack(sum, ref arrdesc, ref result[rquant]); ArShow("\n*** result.Length = " + result.Length, arrdesc, result[rquant]); } }

Result:

 sum = 10
 issue array: 6 1 6 2 4 3 1 2 2 3 2

 *** result.Length = 0
 sorted array: 6 6 4 3 3 2 2 2 2 1 1

 *** result.Length = 1
 last group: 6 4
 data array: 6 3 3 2 2 2 2 1 1

 *** result.Length = 2
 last group: 6 3 1
 data array: 3 2 2 2 2 1

 *** result.Length = 3
 last group: 3 2 2 2 1
 data array: 2

 *** result.Length = 4
 last group: 2
 data array: