3

Имеется список/массив произвольной длины с целочисленными значениями. Необходимо составить из элементов минимальное количество групп, в которых сумма чисел не больше заданного значения. Есть написанный алгоритм, который сортирует и формирует данные группы, но он достаточно громоздкий и может медленно работать в случае большого количества данных. Есть ли смысл для решения использовать искусственную нейронную сеть? Возможно ли ее натренировать, если входные данные и максимальная сумма чисел в группе может быть любой?

Пример:
Входные данные:
Список чисел: [6, 1, 6, 2, 4, 3, 1, 2, 2, 3, 2].
Максимальная сумма группы: 10.
Задача: сформировать минимальное количество групп, все группы должны быть максимально заполнены, кроме одной (минимальный остаток).
Правильный ответ: [1, 1, 2, 6], [2, 2, 6], [3, 3, 4], [2]
Решение: Сумма чисел в списке равна 32. Соответственно, минимальное число групп - 4; минимальный остаток - 2; 3 группы чисел, где сумма чисел равна 10. Проблема в том, что таких чисел может быть очень много и не все можно идеально разложить по группам.
Задачу я решил без каких-либо шаблонов программирования. Мне просто интересны возможность и целесообразность использования ИНС или чего-либо подобного для более качественного решения задачи.

7
  • каким образом тут может помочь нейронная сеть?
    – Grundy
    27 ноя 2017 в 9:50
  • @Grundy, кластеризация же?
    – Qwertiy
    27 ноя 2017 в 9:53
  • 6
    Подозреваю, что при наличии точных алгоритмов, нейронные сети вообще использовать не стоит.
    – Qwertiy
    27 ноя 2017 в 9:55
  • @Qwertiy♦, спасибо за мнение. Как я понимаю, основная проблема кластерного анализа будет заключаться в неопределенном количестве классов-групп чисел. Архитектура такой сети будет крайне сложная.
    – Alex Ross
    27 ноя 2017 в 10:10
  • 2
    Нейронная сеть — это всего лишь последовательность свёрток, то есть взвешенных сумм (в придачу, с участием дробных чисел). Так что, думаю, смысла нет. 27 ноя 2017 в 11:51

1 ответ 1

1

Рассматриваемая задача - обобщение известной задачи о ранце, для решения которой ИНС обычно не применяют.

В то же время можно порекомендовать "жадные" стратегии, не использованные в ОП, при которых заполнение массивов ведётся перебором в порядке убывания элементов.

Вариант реализации (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]);
        }
    }

Результат:

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:

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.