Имеется список/массив произвольной длины с целочисленными значениями. Необходимо составить из элементов минимальное количество групп, в которых сумма чисел не больше заданного значения. Есть написанный алгоритм, который сортирует и формирует данные группы, но он достаточно громоздкий и может медленно работать в случае большого количества данных. Есть ли смысл для решения использовать искусственную нейронную сеть? Возможно ли ее натренировать, если входные данные и максимальная сумма чисел в группе может быть любой?
Пример:
Входные данные:
Список чисел: [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.
Проблема в том, что таких чисел может быть очень много и не все можно идеально разложить по группам.
Задачу я решил без каких-либо шаблонов программирования. Мне просто интересны возможность и целесообразность использования ИНС или чего-либо подобного для более качественного решения задачи.
Ответ
Рассматриваемая задача - обобщение известной задачи о ранце, для решения которой ИНС обычно не применяют.
В то же время можно порекомендовать "жадные" стратегии, не использованные в ОП, при которых заполнение массивов ведётся перебором в порядке убывания элементов.
Вариант реализации (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 + "
last group: ");
foreach (int val in res)
{
Console.Write(" " + val);
}
Console.Write("
data 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("
sum = {0}
issue array: ", sum);
foreach (int val in arr)
Console.Write(" " + val);
Console.WriteLine("
***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("
*** 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:
Комментариев нет:
Отправить комментарий