对于蛮力方法，您首先必须找到 n 的所有 k 个分区。10的所有2个分区是{{9，1}，{8，2}，{7，3}，{6，4}，{5，5}}。10的所有5个分区是{{6，1，1，1}，{5，2，1，1}，{4，3，1，1}，{4，2，2，1，1}，{3，3，2，1，1}，{3，2，2，2，1}，{2，2，2，2}}。这些可以用一个简单的递归函数生成。
对于每个分区，用这些分区生成所有唯一子集，并测试它们是否为目标函数的最小值。例如，对于{4，2，2，1，1}，从4开始，生成所有10！f（4！6！）= 210个4的子集。在每种情况下，剩下的6个元素都可以生成所有6个！f（2！2！2！2！）= 45个唯一的2的子集对。剩下的2个分别放在剩下的两个1插槽中。然后总共有210*45 = 9450个排列要测试该分区。
10的所有7个5分区的排列总数仅为42525。对于10的所有五个2分区，存在511个布置。然后，所给出的示例很容易服从这种蛮力方法。虽然我怀疑有一个更经济的搜索解决方案，这将更适合于更大的向量，其中安排的数量将呈指数增长。
答案是：

{{3521578, 19046274, 20919844, 37860789, 63230795}, {5815341, 29795141, 30498450, 37513838, 41263743}}

字符串
和/或

{{12375813, 61767889}, {17262225, 61080136}, {22105410, 60645182}, {29881559, 42566460}, {34309213, 38950048}}

型

我试着自己写一个解决方案，我想出了这个。

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

#define FIRST_SET_LEN 10
#define SECOND_SET_LEN 10

uint64_t min_sum_square_subsets(const uint64_t* set, size_t set_len, uint32_t subset_count) {
    const size_t subset_len = set_len / subset_count;

    uint64_t result = 0;
    uint64_t curr_subset_sum = 0;

    for (size_t i = 0; i < set_len; i++) {
        if (i % subset_len == 0) {
            result += curr_subset_sum * curr_subset_sum;
            curr_subset_sum = 0;
        }

        curr_subset_sum += set[i];
    }

    result += curr_subset_sum * curr_subset_sum;

    return result;
}

int main(void) {
    const uint32_t first_subset_count = 2;

    const uint64_t first_set[FIRST_SET_LEN] = {
        63230795, 3521578,
        37513838, 37860789,
        30498450, 29795141,
        41263743, 5815341,
        19046274, 20919844
    };

    const uint64_t first_result = min_sum_square_subsets(first_set, FIRST_SET_LEN, first_subset_count);

    printf("First minimum sum of squares of subsets: %llu\n", first_result);
    printf("First expected result: %llu\n", 41895269854617569);

    printf("----------\n");

    const uint32_t second_subset_count = 5;

    const uint64_t second_set[SECOND_SET_LEN] = {
        42566460, 61080136,
        12375813, 29881559,
        61767889, 60645182,
        22105410, 17262225,
        34309213, 38950048
    };

    const uint64_t second_result = min_sum_square_subsets(second_set, SECOND_SET_LEN, second_subset_count);

    printf("Second minimum sum of squares of subsets: %llu\n", second_result);
    printf("Second expected result: %llu\n", 29098109328960071);

    return 0;
}

字符串
结果与预期的结果不符。但我希望它仍然能帮助你。

溶胶

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

uint64_t befsq[10] = {0}, arr[20], min = UINT64_MAX, avg;
int n, m, len[10] = {0};
int find(int cur){
    uint64_t s = 0;
    for (int i = 0; i < m; i++) s += befsq[i]*befsq[i];
    if (s >= min) return 0;
    if (cur == n){
        min = s;
        return 0;
    }
    for (int i = 0; i < m; i++){
        if (befsq[i] > avg)
            continue;
        if (befsq[i]+arr[cur] > avg){
            if (befsq[i]+arr[cur]-avg > (avg-befsq[i]))
                continue;
        }
        len[i]++;
        befsq[i] += arr[cur];
        find(cur+1);
        befsq[i] -= arr[cur];
        len[i]--;
        if (!len[i]) return 0;
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%llu", &arr[i]), avg += arr[i];
    avg /= m;
    find(0);
    printf("%llu", min);
}

字符串
最后，我想出了解决办法。这个想法是试图将每个元素分布到每个子集。同样，用一些“切割”来减少搜索树。这里的“切割”是子集的总和越接近平均值，最小值越小。此外，情况具有的子集越多，最小值越小。所以一旦发现一个子集没有元素，函数就直接返回。这些都是我的观察，我不确定是否所有类似的问题都是如此。希望有人能证实我的想法。- 谢谢-谢谢