如何找到一系列数字的最小差值和？ [英] How do I find the minimum difference sum of a sequence of numbers?

问题描述

我们已经列出了N个数字。



然后我们创建3个分区A，B和C（这可能只是整数）。我们希望将数字存储在三个分区中，使得具有最大总和的分区与第二个和第三个总和具有最小差异。所以我们希望以这种方式存储数字，以便所有分区的总和尽可能地彼此接近。我们应该存储数字的方式是线性的。我的意思是每个总和都应该有一个与其他序列相邻的数字。我不知道你是否理解我，如果有人，请正确编辑我的问题。



我将举例说明如何。



假设我们有以下数字： 8 5 4 3 2 1 3



最好的解决方案是：

We have given a list of N numbers.

We then create 3 partitions A, B and C (thse can be just integers). We want to store the numbers in the three partitions in such way that the partition with the biggest sum to have the least minimum difference from the second and the third sum. So we want to store the numbers in that way so the sum of all partitions to be as close as possible between each other. The way we should store the numbers is linear. By that I mean every sum should have numbers that are one-next-to-the-other sequence. I don't know if you understand me so if someone has, please edit my question properly.

I will provide an example bellow to show you how.

Let's say we have the following numbers : 8 5 4 3 2 1 3

The best solution is :

A = 8
B = 5 + 4 = 9
C = 3 + 2 + 1 + 3 = 9

我想创建问题的线性复杂性解决方案，但我不知道如何。我创建了一个O（n ^ 2）解决方案，但我想确定是否有更好的解决方案。也许是logarythmic。我不想上传我的代码只是为了不让你们迷惑。如果你想，那么我会。



我想要的解决方案可以用C语言提供，也可以只用算法提供！



这是我的查看哪个是假的，绝不应该以该逻辑为基础。我测试了很多测试用语来说这个！

I wanted to create a linear complexity solution of the problem but I don't know how. I created a O(n^2) solution but I wanted to sure if there is better solution. maybe logarythmic. I wan't upload my code just not to confuse you guys. If you want then I will.

The solution I want can be provided in C or just in an algorithm!

This is my view which is false and in no way you should base in that logic. I test many testcases to say that!

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int sum_array(const int* array, int cnt)
{
    int res;
    for ( res = 0; cnt; --cnt)
        res += *array++;
    return res;
}


struct Partition {
    const int *begin;
    const int *end;
    int sum;
};

int indexOfMax(const struct Partition *p, int partcount)
{
    int i, maxIndex;
    for (i = maxIndex = 0; i < partcount; ++i) {
        if (p[i].sum > p[maxIndex].sum)
            maxIndex = i;
    }
    return maxIndex;
}

// give a number to the partition to the right of t if possible
// and return the max of the two adjusted sums
int giveRight(struct Partition *p, int partcount, int t)
{
    if (t >= partcount || t < 0)
        return INT_MAX;
    // only adjust if there is a right partition and we have more than one element
    if (t+1 >= partcount || (p[t].end - p[t].begin == 1))
        return p[t].sum;
    p[t+1].begin = --p[t].end;
    // n is the number we're moving
    int n = *p[t+1].begin;
    p[t].sum -= n;
    p[t+1].sum += n;
    if (p[t].sum > p[t+1].sum)
        return p[t].sum;
    return p[t+1].sum;
}

// give a number to the partition to the left of t if possible
// and return the new sum
int giveLeft(struct Partition *p, int partcount, int t)
{
    if (t >= partcount || t < 0)
        return INT_MAX;
    // only adjust if there is a left partition and we have more than one element
    if (t-1 < 0 || (p[t].end - p[t].begin == 1))
        return p[t].sum;
    // n is the number we're moving
    int n = *p[t].begin;
    p[t-1].end = ++p[t].begin;
    p[t].sum -= n;
    p[t-1].sum += n;
    if (p[t].sum > p[t-1].sum)
        return p[t].sum;
    return p[t-1].sum;
}
#define PART_COUNT 3

int minmax(const int *array, int N)
{
    const int sum = sum_array(array, N);
    struct Partition p[PART_COUNT] = {
        {&array[0], &array[1], array[0]},
        {&array[1], &array[2], array[1]},
        {&array[2], &array[N], sum - array[0] - array[1]}
    };
    int max, maxIndex, test;
    do {
        maxIndex = indexOfMax(p, PART_COUNT);
        max = p[maxIndex].sum;
        test = giveLeft(p, PART_COUNT, maxIndex);
        if (test >= max) {
            // not improved, but try one more
            giveLeft(p, PART_COUNT, maxIndex-1);
            test = p[indexOfMax(p, PART_COUNT)].sum;
            if (test >= max) {
                // not improved so reverse this move
                giveRight(p, PART_COUNT, maxIndex-2);
                giveRight(p, PART_COUNT, maxIndex-1);
                // and try the right
                test = giveRight(p, PART_COUNT, maxIndex);
                if (test >= max) {
                    // not improved but try one more
                    giveRight(p, PART_COUNT, maxIndex+1);
                    test = p[indexOfMax(p, PART_COUNT)].sum;
                    if (test >= max) {
                        // not improved, so reverse this move
                        giveLeft(p, PART_COUNT, maxIndex+2);
                        giveLeft(p, PART_COUNT, maxIndex+1);
                    }
                }
            }
        }
    } while (test < max);
    return max;
}

int main()
{
    int N = 0;
    FILE* input = fopen("share.in","r");

    fscanf(input,"%d",&N);

    int *array = malloc(N * sizeof(int));
    if (array != NULL) {
        for (int i = 0; i < N; i++) {
            fscanf(input,"%i",&array[i]);
        }
    }
    fclose(input);

    printf("%d\n", minmax(array, N));
    free(array);
}

推荐答案

一种可能的方法（不一定是最优的 - 这需要更深入的分析）是计算在剩余垃圾箱中展开的剩余数字的平均值，并按顺序填充每个垃圾箱，直到添加比不添加当前垃圾箱更糟糕 - 然后转到下一个垃圾箱。

Eg

A possible approach (which is not necessarily optimal - this would require a deeper analysis) is to calculate the average of the remaining numbers for spreading over the remaining bins and fill each bin in sequence until adding is worse than not adding for the current bin - then go to the next bin.
E.g.

0) Calculate the average of the remaining numbers and the remaining bins.
1) If the current bin is empty, add the first of the remaining numbers to the current bin.
2) Try to add the next remaining number to the current bin.
2.1) If adding is increasing the distance to the average, reject adding and go to 3).
2.2) Else, add the number and go to 2).
3) If current bin is not last bin, move to the next bin and go to 0).
4) Else, add the remaining numbers to the current bin.
5) Done.

干杯

Andi

PS：要保持整数域，你可以在剩余的数字和探针加上乘以剩余的数量（加上当前的bin），然后将该数字与不添加数字进行比较。

Eg

Cheers
Andi
PS: To stay in the integer number domain, you can work on the sum of the remaining numbers and probe adding by multiplying by the number of remaining (plus current bin) and then compare that number against not adding the number.
E.g.

S  = 8 5 4 3 2 1 3
N  = 3

S0 = 26 (8+5+4+3+2+1+3)
B0 = 8       -> Delta = Abs(B0*N - S0) = 2
B0 = 8+5     -> Delta = Abs(B0*N - S0) = 13 -> reject
B0 = 8

N--
S1 = S0-B0 = 18 (5+4+3+2+1+3)
B1 = 5       -> Delta = Abs(B1*N - S1) = 8
B1 = 5+4     -> Delta = Abs(B1*N - S1) = 0
B1 = 5+4+3   -> Delta = Abs(B1*N - S1) = 6 -> reject
B1 = 5+4

N--
S2 = S1-B1 = 9 (3+2+1+3)
B2 = 3       -> Delta = Abs(B2*N - S2) = 6
B2 = 3+2     -> Delta = Abs(B2*N - S2) = 4
B2 = 3+2+1   -> Delta = Abs(B2*N - S2) = 3
B2 = 3+2+1+3 -> Delta = Abs(B2*N - S2) = 0
B2 = 3+2+1+3

这篇关于如何找到一系列数字的最小差值和？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！