寻找 x 个子数组，使得这些子数组的总和最小。

Question

寻找一定数量的非重叠连续子数组，使得这些子数组的总和最小，并且所有元素总计为 y。

Example 1:
Input: {2,1, 10, 40, 5, 6} , x=2, y=4
Output: {{2,1},{5,6}}

---

Example 2:
Input: {2,1, 10, 40, 5, 6} , x=1, y=2
Output: {{2,1}}

---

Example 3:
Input: {2,1, 10, 40, 5, 6} , x=1, y=3
Output: {{2,1,10}}

---

Example 4:
Input: {2,1, 10, 40, 5, 6} , x=1000, y=3
Output: {{2},{1},{5}} or {{2,1},{5}}

我在互联网上进行了搜索，但未找到类似的问题。所以我自己设计了算法。不幸的是，时间复杂度是指数级别的。我不会提供我的解决方案，因为我已经形成了一种思维定势，希望从零开始尝试新的思路。

所以，我的问题是：您知道一种尽可能高效解决此问题的算法吗？

非常感谢您提供任何帮助！

P.S. 提醒一下，请不要低估问题的复杂性。

- user7138304

---

你应该定义x和y。不清楚它们是什么。 - Nir Alfasi

请查看“背包问题”。 - Ronnis

x 是什么？是子数组数量的上限吗？ - DAle

正如其他人所说，你对 x 的定义与最后一个示例不符。你说它是子数组的数量，但在最后一个示例中它并不是。你不能期望对一个定义不清的问题得到有用的答案。 - Gene

x是要找到的子数组的最大数量吗？ - Luca Reccia

Answer 1

这是我尝试应用DP方法的结果。

令M(I, Y, X, L)表示子数组的最小总和，其中：

- I - 我们使用原始数组ARR的前I个元素 - Y - 子数组中所有元素的计数 - X - 子数组数量的上限 - 如果最后一个（第I个）元素包含在形成最小值的子数组中，则L = 1，否则L = 0 然后使用以下公式： M(I, Y, X, 1) = ARR[I] + MIN(M(I-1, Y-1, X, 1), M(I-1, Y-1, X-1, 0)) 和 M(I, Y, X, 0) = MIN(M(I-1, Y, X, 1), M(I-1, Y, X, 0))

- algrid

Answer 2

[使用动态规划的新解决方案]

我花了很多时间在这上面，希望它能够很好地工作。像往常一样，我进行了注释以使其更加清晰易懂。希望这可以帮到你，我没有找到更有效的方法，抱歉。

package temp2;

public class Main {
    private static int
            X=1, //This i understood is the max number of subarray. Change it to find counterexample.
            Y=2, //This is the number of elements you want as result. Change it to find counterexample.
            VERY_LARGE_NUMBER=1000000;

    private static int array[] = {1, 100, 2, 2, 100, 1}; //just your array. Change it to find counterexample. Remember to leave the bounds (9999) as i explained in the answer.



    public static void main(String args[]){
        System.out.println("Obtained result: "+alg(array.length-1, 0, 0, 0, false));
    }

    public static int alg(int index, int partialSum, int numberOfUsedArrays, int numberOfUsedElements, boolean beforeIsInResults){

        /**
         * If the remaning number to analize are equal than the max number of elements minus the number of elements found AND
         * i can add them to the results adding a new subarray OR using the adjacent one, i add all the value to the result sum.
         */
        if(index+1+numberOfUsedElements == Y && (numberOfUsedArrays<X || (beforeIsInResults && numberOfUsedArrays<=X))){
            int summ = 0;
            for(int i=0; i<=index; i++)
                summ+=array[i];
            return summ+partialSum;
        }

        /**
         * If i don't have any subarray to create or to use (if is possible to connect to the adjacent) AND i don't enough elements
         * in the computed solution i don't consider this solution.
         */
        if((((numberOfUsedArrays > X && beforeIsInResults) || (numberOfUsedArrays >= X && !beforeIsInResults)) && numberOfUsedElements < Y )){   //Old condition i think is no more needed: || (index+1+numberOfUsedElements == Y && ((numberOfUsedArrays > X && beforeIsInResults) || (numberOfUsedArrays >= X && !beforeIsInResults)))){
            return VERY_LARGE_NUMBER;
        }

        /**
         * If the index is out of bound OR i don't have any more subarrays left OR i reach the max number of element of the result i return the computed solution.
         */
        if( index < 0 || ((numberOfUsedArrays > X && beforeIsInResults) || (numberOfUsedArrays >= X && !beforeIsInResults)) || numberOfUsedElements >= Y )
            return partialSum;


        /**
         * I check if the best solution contains OR not contain the selected index. The only difference from if to else is that in case in which i choose to
         * add the element to the result is the element computed before (index+1) was selected no new array has been used else i need to update the number of array used.  
         */
        if(beforeIsInResults)
            return Math.min(
                    alg(index-1, partialSum+array[index], numberOfUsedArrays, numberOfUsedElements+1, true),
                    alg(index-1, partialSum, numberOfUsedArrays, numberOfUsedElements, false));
        else
            return Math.min(
                    alg(index-1, partialSum+array[index], numberOfUsedArrays+1, numberOfUsedElements+1, true),
                    alg(index-1, partialSum, numberOfUsedArrays, numberOfUsedElements, false));
    }
}

[旧的不起作用的解决方案]: 计数器示例：{1, 100, 2, 2, 100, 1} x = 1，y = 2

我找到了这个算法。除非我弄错了，复杂度应该是O(Y×数组长度)。

注意：所有这些都假设您的X变量意味着“子数组的最大数量”。

Start: Find min in array not in result
       add it to result
       did we reach the max number of result?
       (Yes: end and print results) (No: go to Continue)

Continue: Compute min subarrays in the results.
          Is it equals to the max subarray (`Y`)?
          (No: go to Start) (Yes:Continue2)

Continue2: Find minimum value near one subarray.
           go to Continue.

我知道这可能有点令人困惑，而且这还不是最糟糕的部分。

我写了以下代码来测试我的算法。这可能是我写过的最糟糕的代码。

我试图保持简单，避免任何“特殊情况控制”，例如，在某些if中应该有控制以避免任何索引超出边界异常（但由于懒惰，我只放置了一些大而无用的值）。

我尝试了所有你的组合，并且它工作正常。我没有找到任何反例。

如果您需要更多澄清，请随时询问（由于在意大利这里是晚上，我将在明天回复）

这是代码：

public class Main {
    public static void main(String[] args){
        int     X=1000, //This i understood is the max number of subarray. Change it to find counterexample.
                Y=3, //This is the number of elements you want as result. Change it to find counterexample.
                temp, //This is just a value i used to store the minimum during the search along the array.
                tempIndex, //This is the one that keeps the index of temp.
                subarray=0, //This value will contain the minimum number of subarrays formed by the results. Since at the start there are no results, there are no subarray either. (to compare with X)
                resultsSize=0; //This will used to store the number of results temporary found (to compare with Y)

        int array[] = {9999,2,1,10,40,5,6,9999}; //just your array. Change it to find counterexample. Remember to leave the bounds (9999) as i explained in the answer.

        /*If my professor saw me use two parallel arrays instead of an array of objects 
         *I think he might kill me, but as I said, I'm lazy and this code just serves to make an example
         */
        boolean used[] = {false, false, false, false, false, false, false, false}; //Just used to chceck if one value is already used in results.

        while(true){
            try{

                //The following code just find the minimum element not used.
                temp=9998;
                tempIndex=-1;
                for(int i=0; i<array.length; i++){
                    if(array[i]<temp && !used[i]){
                        temp=array[i];
                        tempIndex=i;
                    }
                }

                //The following code add the found number to the results (just print it)
                used[tempIndex] = true;
                resultsSize++;
                System.out.print(temp+" ");

                //This is one of the two way to return with success. Basically we return when we found Y results.
                if(resultsSize == Y ) {
                    System.out.println("\nDone.");
                    return;
                }

                /*When i add an element to the result 3 things may happen.
                 *The result isn't near to any result, so it would create a new subarray
                 *The result is near to just one result, no new subarray created
                 *The result is just in the middle of two other result, adding it will result in fusion on two subarrays into one.
                 *The following code just use this rule to compute the subarray number
                 */
                if(used[tempIndex-1] && used[tempIndex+1]){ //third case
                    subarray--;
                }else if(!used[tempIndex-1] && !used[tempIndex+1]){ //first case
                    subarray++;
                }

                /*The following code will be executed only IF we reach the limit of subarrays. If so, he just try to add the smallest element without
                 *any subarray increment. If the subarrays get decremented (third case of the comment above) the while ends and the control returns back to the
                 *up side of this function early discussed.
                 */
                while(subarray == X){

                    //The following code just find the minimum element not used.
                    temp=9998;
                    tempIndex=-1;
                    for(int i=0; i<array.length; i++){
                        if(array[i]<temp && !used[i] && (used[i-1] || used[i+1])){
                            temp=array[i];
                            tempIndex=i;
                        }
                    }

                    //If this is true there are no minimum element near results which practically means that your 'Y' value is bigger than the length of the array
                    if(temp==9998){
                        System.out.println("\nYou shloud not ever come here.\ncheck if your 'Y' value is bigger than the length of the array");
                        return;
                    }

                    //The following code add the found number to the results (just print it)
                    used[tempIndex] = true;
                    resultsSize++;
                    System.out.print(temp+" ");

                    //This is one of the two way to return with success. Basically we return when we found Y results.
                    if(resultsSize == Y ){
                        System.out.println("\nDone.");
                        return;
                    }

                    //The following code checks with the new added result the number of subarrays get decremented.
                    //Remember that if subarrays get decremented the alg go back to the first part and search for minimum even non near to an existing subarray.
                    if(used[tempIndex-1] && used[tempIndex+1]){
                        subarray--;
                    }
                }
            } catch(Throwable e){ //Used for debugging, no more needed.

                e.printStackTrace();
                return;
            }
        }
    }
}

如果这篇文章对你有用，或者只是浪费了你的时间，请告诉我；）

- Luca Reccia

---

抱歉，但这显然是错误的贪心算法。反例为{1, 100, 2, 2, 100, 1}，x = 1，y = 2。 - DAle

你说得对，我会尝试绕过那个问题。 - Luca Reccia

我怀疑贪心算法能否解决这个问题。 - DAle

是的，我也开始怀疑了XD实际上我正在尝试寻找一些不同的方法。 - Luca Reccia