c - 将时间分成两个盒子并找到最小差异

Question

开始学习递归，我被这个简单的问题困住了。我相信有更优化的方法可以做到这一点，但我首先要尝试学习暴力破解方法。

我有包 A 和包 B，并且有 n 件元素，每件都有一些时间(带两位小数的 float )。思路是按两个袋子分配元素，求两个袋子的差值最小。这个想法是尝试所有可能的结果。

我想只在一个袋子里(假设是袋子 A)，因为另一个袋子将包含所有不在袋子 A 中的元素，因此差值将是总和的绝对值乘以总和 - 2 * 总和包A中的元素时间。

我这样调用我的递归函数:

min = total_time;
recursive(0, items_number - 1, 0);

函数的代码是这样的:

void recursive(int index, int step, float sum) {
    sum += items_time[index];
    float difference = fabs(total_time - 2 * sum);

    if (min > difference) {
        min = difference;
    }

    if (!(min == 0.00 || step == 1 || sum > middle_time)) {
        int i;
        for (i = 0; i < items_number; i++) {
            if (i != index) {
                recursive(i, step - 1, sum);
            }
        }
    }
}

假设我有 4 个时间为 1.23, 2.17, 2.95, 2.31

我得到的结果是 0.30。我相信这是正确的结果，但我几乎可以肯定，如果它是纯粹的改变，因为如果我尝试更大的情况，程序会在一段时间后停止。可能是因为递归树变大了。

谁能给我指明方向？

Answer 1

好的，在澄清之后，让我(希望)为您指出一个方向:

假设您知道 n 是什么，在 n items 中提到。在您的示例中，2n 是 4，因此 n = 2。让我们再选一个 n，这次设为 3，我们的 time 应该是:

1.00
2.00
3.00
4.00
5.00
6.00

现在，我们已经知道答案是什么了；你说的都是正确的，最好每个袋子的 n = 3 time 总和为 middle_time，即 21/2 = 10.5 在这种情况下。由于整数可能永远不会和带小数点的数字相加，因此 10.5 : 10.5 在此示例中可能永远无法实现，但 10 : 11 可以，并且您可以拥有 10 到 6.00 + 3.00 + 1.00(3 个元素)，所以...是的，答案就是 1。

你会让计算机如何计算它？出色地;回想一下我一开始说的话:

Let us assume that you know what n is.

在那种情况下，天真的程序员可能会简单地将所有这些放在 2 或 3 个嵌套的 for 循环中。 2 如果他/她知道另一半将在您选择一半时确定(通过简单地固定我们组中的第一个元素，因为该元素将包含在其中一个组中) ，就像你也知道； 3 如果他/她不知道。让我们用 2 来实现:

...
float difference;
int i;
for ( i = 1; i < items_number; i++ ) {
    sum = items_time[0] + items_time[i];
    int j;
    for ( j = i + 1; j < items_number; j++ ) {
        sum += items_time[j];
        difference = fabs( total_time - 2 * sum );
        if ( min > difference ) {
            min = difference;
        }
    }
}
...

让我稍微评论一下代码以便更快地理解:在第一个循环中，它将第 0 次、第 1 次和第 2 次相加，如您所见；然后它将执行与您所做的相同的检查(计算 difference 并将其与 min 进行比较)。让我们称其为 012 组。下一个要检查的组将是 013，然后是 014，然后是 015；然后 023，依此类推...将检查将 6 分成两个 3 的每个可能组合。

这个操作对电脑来说应该不会有什么麻烦。即使使用这种简单的方法，最大尝试次数也将是 3 与 6 个唯一元素的组合除以 2。在数学中，人们将其表示为 C(6, 3) ，计算结果为 (6 * 5 * 4)/(3 * 2 * 1) = 20；除以 2，所以它是 10。

我的猜测是，即使 n 为 10，计算机也不会造成问题，从而使组合数量高达 C(20, 10) / 2 = 92 378。 .但是，手动写下 9 个嵌套的 for 循环对您来说是个问题...

无论如何，好处是，您可以递归地嵌套这些循环。在这里我将结束我的指导。由于您显然已经在研究递归，所以此时提供解决方案对我来说不是一件好事。我可以向您保证这是可行的。

此外，我自己制作的版本可以在一秒钟内完成最多 items_number = 22，而无需进行任何优化；简单地用蛮力。这使得 352 716组合，而我的机器只是一个简单的 Windows 平板电脑...