Сумма частичной группы {? ^ (0), ? (1), ……, ? (?)}

Question

Я хочу написать программу, в которой входными данными являются x и y целочисленные значения, а затем:

1. Пусть s будет набором {x ⁰ , ? ¹ ,…, ? ^y };сохраните его в array.

2. Повтор:

   • Разделите набор s на два подмножества: s1 и s2.
   • Найти сумму каждого из двух подмножеств и сохранить их в переменных, таких как sum1, sum2.
   • Рассчитать произведение sum1 * sum2.
3. Программа заканчивается после прохождения по всем частичным группам, которые могут быть сформированы, и затем печатает максимальное значение продукта 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;
}

Answer 1

Это не проблема программирования, это проблема комбинаторики с теоретическим, а не эмпирическим подходом к ее решению.Вы можете просто напечатать правильное решение и не перебирать любые разделы.

Почему это так?

Let

т.е. 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-полной.Это очень грубо означает, что не существует решения, которое было бы гораздо более эффективным, чем просто пробовать все возможные комбинации.

Answer 2

Вот дурацкий генератор «все комбинации предоставленных аргументов», предоставленный без комментариев и объяснений, потому что я думаю, что это домашнее задание, и здесь важно понять, как и почему это делает то, что он делает.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(int c, const char **v)
{
    basic_string<const char *> options(v);
    auto N(options.length());
    for (auto n = 1u; n < N; ++n) {
        vector<char> pick(N);
        fill_n(pick.rbegin(), n, 1);
        do for (auto j=1u; j<N; ++j)
            if (pick[j])
                cout << options[j]<<' ';
        while (cout<<'\n', next_permutation(begin(pick)+1, end(pick)));
    }
}