Блог

У меня есть список номеров, которые я пытаюсь эффективно отсортировать по группам разного размера. Размеры моей группы-1000, 500, 300 человек. Это проблема с упаковкой мусора. Итак, если у меня есть список с

250, 100

Я бы использовал группу размером 300, так как разница между общей суммой списка и общей емкостью бункера-это «отходы».

Таким образом, для списка, который составил 1600, лучшее, что можно сделать, — это 1 1000, 1 500 и 1 300.

У меня есть логика, чтобы определить, какой размер ячейки использовать, учитывая оставшуюся сумму.

Поскольку в моем случае важен порядок списка, я не могу просто отсортировать его по величине, а затем по пакету. список, который является

85, 100, 240, …

Нужно оставаться в таком порядке. Поэтому, чтобы эффективно упаковаться, я начинаю с того, что беру с начала списка столько номеров, сколько поместится в данной группе, удаляя их из списка, чтобы они не использовались дважды.

Проблема в том, что когда я иду вызывать рекурсивную функцию, я хочу передать ей список оставшихся номеров для использования.

Проблема, с которой я сталкиваюсь, заключается в том, что список, который я передаю в рекурсивный файл, передается по ссылке, поэтому любые изменения, произошедшие в более поздней рекурсии, все еще присутствуют в более ранней. Как я мог бы обойти эту проблему в C#?

Редактировать: Я добавляю больше примеров, чтобы, надеюсь, более полно объяснить свою проблему

Это будет долго, поэтому я приношу свои извинения. Я приведу длинный пример, который показывает мою дилемму.

Скажем, у меня есть список

100, 115, 105, 205, 195, 240, 240, 130, 180, 140, 225, 85

В общей сложности это 1960 год. Поэтому я хочу создать 2 1000 групп. Для коэффициента безопасности добавлено 15, поэтому каждая группа начинается с 15.

Если я начну с начала списка и возьму номера, я получу такую группу

Что осталось от первоначального списка : 240, 130, 180, 140, 225, 85 всего осталось 1000

группа 1 : 15, 100, 115, 105, 205, 195, 240 всего 975

Оставшаяся сумма составляет 1000, которая при следующей попытке рекурсии создать вторую группу 1000 останется с 85, что приведет к сбою.

Таким образом, алгоритм состоит в том, чтобы вернуться в группу 1 («прогресс» со второй итерации групп теперь исчез), удалить последнее число, а затем начать просматривать оставшийся список, чтобы найти следующее первое число, которое подошло бы.

В этом случае последние 240 из группы 1 будут удалены и заменены следующими 240 в списке, поэтому следующая итерация группы 2 снова завершится неудачно.

Таким образом, «прогресс» с этой итерации группы 2 будет удален, вернитесь в группу 1 и удалите 240. Теперь первая группа и остальные выглядят так

Оставшиеся : 240, 240, 130, 180, 140, 225, 85

Группа 1 : 15, 100, 115, 105, 205, 195

Следующая итерация должна затем взять 130, а затем 85, которые затем составят группу из 950, так что оставшееся равно 1025 и снова не подойдет.

И так далее, и тому подобное. Проблема, с которой я сталкиваюсь, заключается в том, что один рекурсивный уровень знает, какие числа он уже пробовал, и знает, как их избежать, в то время как следующая итерация не позволяет избежать тех, которых избежал предыдущий. Когда группа 1 удаляет 240 из своего списка и возвращает его оставшимся, когда группа 2 начинает выбирать из списка, она будет начинаться с 240, так как она будет первой в списке

Решением с этим списком в конце концов было бы

Группа 1 : 15, 100, 115, 105, 205, 195, 180, 85

Группа 2: 15, 240, 240, 130, 140, 225

Вы можете попытаться клонировать список всякий раз, когда вызываете рекурсивную функцию, и передавать только что созданный клон вместо исходного списка. Это может выглядеть примерно так:

 public List<int> RecursiveFunction(List<int> listOfRemainingNumbers)
{
    // Do some logic
    List<int> numbers = new List<int>();
    List<int> clone = new List<int>(numbers);
    return RecursiveFunction(clone);
}
 

Пожалуйста, обратите внимание, что на самом деле это не очень эффективный подход. Особенно если ваши списки очень велики и содержат несколько тысяч элементов, такой подход потребует много памяти.
Более эффективный подход может заключаться в том, чтобы не использовать рекурсию, а вместо этого использовать простой цикл и пытаться не удалять элементы из списка, возможно, используя out ключевое слово для получения дополнительного «возвращаемого значения» от вашей функции.

Ты слишком стараешься? или вы, возможно, не знакомы с Linq, который является очень мощным…

 List<int> n = new List<int>() { 432, 12398, 38, 438, 865, 2, 38, 716, 9421, 347, 550 };
var n2 = n.OrderBy(num => num).ToList();
 

убедитесь, что вы добавили в начало своего кода…

 using System.Linq;
 

Вы можете быть удивлены, как быстро он возвращает список без контроля какой-либо рекурсии или разделения на второстепенные группы.