c++ - {^(0),(1),……,()} 的部分群之和

Question

我想编写一个程序，其中输入是整数值，然后x：y

1. 设 s 为集合 { x ⁰ , ¹ , ..., ^y }; 将其存储在array.

2. 重复：

   • 将集合s分成两个子集：s1和s2。
   • 求两个子集的总和，并将它们存储在变量中，如sum1, sum2。
   • 计算 的乘积sum1 * sum2。
3. 程序在遍历所有可以形成的部分组后结束，然后打印 product 的最大值sum1 * sum2。示例：假设 x=2 , y=3 s= {1,2,4,8} 其中一个除法是取 s1 ={1,4} , s2={2,8} sum1=5 , sum2= 10乘积为 50，将与以相同方式计算的其他乘积进行比较，例如 s1 ={1} 、 s2={2,4,8} sum1=1 、 sum2=14 和乘积为 14 等等.

到目前为止我的代码：

#include <iostream>
using namespace std;

int main () 
{
    int a[10000]; // Max value expected.
    int x;
    int y;
    cin >> x;
    cin >> y;
    int xexpy = 1;
    int k;

    for (int i = 0; i <= y; i++)
    {
        xexpy = 1;
        k = i;

        while(k > 0)
        { 
            xexpy = xexpy * x;
            k--;
        }

        cout << "\n" << xexpy;
        a[i] = xexpy;
    }

    return 0;
}

标签： c++arraysrecursionconsolecombinations

Answer 1

这不是一个编程问题，它是一个组合问题，它的解决方案是理论而不是经验方法。您可以简单地打印正确的解决方案，而不必费心遍历任何分区。

这是为什么？

让

即 z 是 s ₁中所有 s 元素之和的分数。它认为

因此，两组的乘积满足：

作为 z 的函数（不是 x 和 y 的函数），这是一条在 z = 1/2 处取最大值的抛物线；并且没有其他局部最大值点，即接近 1/2 必然会增加该乘积。因此，您要做的是对整个集合进行分区，以使 s ₁和 s ₂中的每一个都尽可能接近以获得元素总和的一半。

通常，您可能不得不使用编程来考虑多个子集，但是由于您的元素是由公式给出的 - 而且它是几何序列的公式。

首先，让我们假设 x >= 2 并且 y >= 2，否则这不是一个有趣的问题。

现在，对于 x >= 2，我们知道

（几何序列的总和），因此

即最后一个元素总是超过所有其他元素放在一起。这就是为什么你总是想选择 {x ^y } 作为 s ₁和所有其他元素作为 s ₂。无需运行任何程序。然后，您还可以轻松计算最佳总和积。

---

注意：如果我们不对 s 的元素做出假设，除了它们是非负整数，那么找到最优解就是Partition 问题的优化版本——它是 NP 完全的。这意味着，非常粗略地说，没有任何解决方案从根本上比尝试所有可能的组合更有效。