我如何跟踪递归期间发生的变化

Question

我有一个数字列表，我正试图将其有效地分类为不同大小的组。我的组大小是 1000、500、300。这是一个装箱问题。所以如果我有一个列表

250, 100

我会使用一个 300 大小的组，因为列表总数和垃圾箱总容量之间的差异是“浪费”。

所以对于总计 1600 的列表，可以完成的最好的是 1 1000、1 500 和 1 300。

根据剩余总量，我有逻辑来确定要使用的垃圾箱大小。

因为在我的例子中，列表的顺序很重要，所以我不能简单地按最大然后按 bin pack 排序。一个列表

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 组（第二组迭代的“进度”现在消失了），删除最后一个数字，然后开始查看剩余列表以找到下一个第一个数字适合。

在这种情况下，第 1 组的最后 240 个将被删除，并替换为列表中的下一个 240 个，因此下一个第 2 组迭代将再次失败。

因此，第 2 组迭代的“进度”将被删除，返回第 1 组并删除 240。现在第 1 组和其余的看起来像这样

剩余：240、240、130、180、140、225、85

第 1 组：15、100、115、105、205、195

下一次迭代应该取 130，然后取 85，这将构成一组 950，因此剩余的是 1025，再次不适合。

等等等等。我遇到的问题是让一个递归级别知道它已经尝试过哪些数字并知道要避免它们，同时下一次迭代不会避免前一个迭代避免的那些。当第 1 组从它的列表中删除 240，returns 剩下的，当第 2 组开始从列表中选择时，它将以 240 开头，因为它将排在列表中的第一个

最后这个列表的解决方案是

第 1 组：15、100、115、105、205、195、180、85

第 2 组：15、240、240、130、140、225

Answer 1

您可以在每次调用递归函数并传递新创建的克隆而不是原始列表时尝试克隆列表。这可能看起来像这样：

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 关键字从中获取额外的“return 值”你的功能。

Answer 2

你是不是太努力了？或者你可能不熟悉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;

您可能会惊讶于 returns 在您不控制任何递归或拆分为次级组的情况下，列表的速度如此之快。

我如何跟踪递归期间发生的变化

How can I keep track of changes that happen during recursion

c#

recursion

pass-by-reference

bin-packing