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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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