在序列中求最小元素之和

Question

我有一组三元组，希望以最小的总和方式将其中的数字相加，且每个三元组只能选择一个数字。例如：

10 10 1   //minimum 1
1  10 21  //minimum 1
10 1  10  //minimum 1 Ans : 1+1+1 = 3

然而，您不能选择同一列中相邻的元素。

10 10 1 //select 1
10 10 1 //cannot select 1, that's adjacent!
10 10 1 //safe to select 1

但问题在于，如果出现平局，我需要扫描序列中的下一个三元组，并确保不选择前一个序列中的数字以获得最大利润。 例如：

10 10 10  // step 2.select 10 from column 1 or 2
10 10 1   // step 1.make sure not to select element in column 3 in previous sequence
          // step 3. select 1 from column 3

由于我们无法替换Scanner的位置，因此我无法将Scanner的readLine移动到上一个位置，那么我该如何提前扫描？

我的想法是：（由于数字范围很大，我使用了BigInt）

for(long j=0; j<noOfTriples ; j++){
    firstNumber = in.nextBigInteger();
    secNumber = in.nextBigInteger();
    thirdNumber = in.nextBigInteger();

    if(areEqual(firstNumber, secNumber, thirdNumber)){
        while(true){
             firstNumber2 = in.nextBigInteger();
             secNumber2 = in.nextBigInteger();
             thirdNumber2 = in.nextBigInteger();
             noOfTriples--;
                if(areEqual(firstNumber2, secNumber2, thirdNumber2)){
                    count.add(secNumber2); // add any number to the count
                                          // since all of them are same
                }else
                    break;
                }   

    pass(firstNumber, secNumber, thirdNumber, least(firstNumber2, secNumber2, thirdNumber2));
    //pass adds up the minimum of three to the count 
    //where the last field indicates which element to NOT use while adding &
    //least returns minimum of the three
    }else
    pass(firstNumber, secNumber, thirdNumber, -1);  //-1 indicates no bias
}

编辑：

1. sprinter 指出，我需要扫描整个三元组列表。仅仅顺序扫描下一个不会有所帮助。
2. 输入数量可能高达一百万，因此穷举搜索无法帮助。

- Mayur Kulkarni

---

这在线性时间内是可行的。重要提示：如果你以某种方式知道了所有前一行 涉及选择前一行第一个数字 的最小总和，以及所有前一行 涉及选择前一行第二个数字 的最小总和，以及所有前一行 涉及选择前一行第三个数字 的最小总和呢？ - j_random_hacker

@j_random_hacker 哦，谢谢，我现在明白了。我应该把所有的变量都存储在LinkedList中，然后迭代所有的数字并更新计数吗？（如果它不是可行的解决方案，也应该丢弃该数字并继续） - Mayur Kulkarni

我不确定你的意思，但我想到的解决方案不需要任何链接列表 - 只需要3个总数，加上当前输入行的3个数字。 - j_random_hacker

我正在使用链表来跟踪先前选择的列，并确保当前时间不包括它。 - Mayur Kulkarni

我的方法的整个理念是不要致力于特定列的选择。其想法是保持每一种选择前一个数字的最佳答案*--此后，仅需在处理完最终输入行后选择最佳的一种即可。 - j_random_hacker

Answer 1

我相信这是一个动态规划问题。

我们需要保留一个状态 F(idx, prev)，其中 idx 表示当前所在的序列，prev 表示你从前一个序列添加的项目编号。因此，我们可以迁移到新状态 F(idx+1, new_prev)，使得根据题目要求 new_prev 不等于 prev。 伪代码：

F(idx, prev) {

     if ( idx == n+1 ) return 0; //Done with shopping on all N triplets

     ans = INFINITY

     for all item_nums from 1 to 3
            if ( item_nums != prev ) ans = min(ans, cost of item_num in shop_num idx + F(idx+1, item_nums)

    return ans
}

- Pournima Bedarkar

Answer 2

您似乎认为只需要向前查看一组数据即可决定选择哪个当前集合以达到最小值。这是不正确的。如果有(9, 3, 5), (8, 4, 7), (6, 1, 8)，那么在查看前两个之后，您会选择5和4。但是一旦考虑到第三组数据，您会发现应该选择7和3，以便您有选择1的选项。实际上，由于最终集合可能具有任意大的数字，直到您查看所有集合之前，您都不知道正确的选择选项。

所有这些的结论是，您需要使用更复杂的算法来最小化总和。考虑到您有许多项目，穷举搜索不是一个选择。但是，让我们从那里开始，以便您可以看到它的样子：

假设您已经读入了所有输入，并将它们存储在一个>>结构中。

int minSum(int index, int previous, List<List<Integer>> inputs) {
    if (index >= inputs.size())
        return 0;
    else
        return IntStream.range(0, 3)
            .filter(n -> n != previousIndex)
            .map(n -> minSum(index + 1, n, inputs)).min();
}

希望您熟悉Java 8并能理解此代码。

由于性能原因，现在需要缩小搜索空间，这使问题变得更加复杂。换句话说，您必须避免搜索那些可以推断出永远不会导致较低总数的选项。

例如，您有集合（1、8、5）、（2、3、6）、（4、9、2）。您的算法查看选项1 + 3 + 4，并获得总数7。它接下来查看的值是第一组中的8。但很明显，根本不需要考虑该选项，因为它已经大于迄今为止最小的总数（即7），因此包括它的任何选项都不可能导致较小的总数。

希望这足以给您提供足够的提示。如果卡住了，请提交关于这些修剪算法的单独问题。

- sprinter

---

是的，抱歉我没有考虑到这一点。我原本计划使用列表或类似的东西来存储元素，但输入的数量可能高达一百万，所以不太实用。 - Mayur Kulkarni

一百万没问题。现代计算机可以轻松处理列表中数百万个项目。如果是十亿，可能会有些棘手！另一方面，这也限制了您可以使用的算法：如果您有一百万个项目，则无法进行所有选项的详尽搜索。 - sprinter

我会在我的回答中加入一些想法。 - sprinter