Реализация разделения массива на 2 части так, чтобы две части имели одинаковое среднее

Я реализую подход, описанный в этот вопрос для той же проблемы, но я не думаю, что это работает.

Для тех, кто не хочет вдаваться в математику, вот суть алгебры:

Average = Sum(S1)/n(S1) = Sum(S2)/ n(S2) = Sum(Total)/n(Total) 

where n() stands for the number of elements in the array & Sum() stands for the cumulative sum

S1 и S2 являются взаимоисключающими подмножествами массива Total. Таким образом, чтобы найти требуемое подмножество, где это условие будет выполняться, мы находим Sum(S1) = Sum(Total) * n(S1)/n(Total)

Мой подход:

#include <bits/stdc++.h>

using namespace std;

bool SubsetSum(vector<int> &A, int Sum)
{
    bool dp[Sum+1][A.size()+1];
    int i, j;
    for(i=0; i<= A.size(); i++)
        dp[0][i] = false; // When sum = 0
    for(i=0; i<=Sum; i++)
        dp[i][0] = 1; // When num of elements = 0
    for(i = 1; i <= A.size(); i++)
    {
        for(j=1; j<= Sum; j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j-A[i-1] >= 0)
                dp[i][j] = dp[i][j] || dp[i-1][j-A[i-1]];
        }
    }
    return dp[Sum][A.size()];
}

void avgset(vector<int> &A) {
    int total = accumulate(A.begin(), A.end(), 0); // Cumulative sum of the vector A
    int ntotal = A.size(); // Total number of elements

    int i;
    for(i=1; i<=ntotal; i++) // Subset size can be anything between 1 to the number of elements in the total subset
    {
        if((total * i) % ntotal == 0)
        {
            if(SubsetSum(A, (total * i)/ntotal)) // Required subset sum = total * i)/ntotal
                cout<<"Array can be broken into 2 arrays each with equal average of "<<(total * i)/ntotal<<endl;
        }
    }
}

int main()
{
    vector<int> A = {1, 7, 15, 29, 11, 9};
    avgset(A);
    return 0;
}

Этот код выводит:

Array can be broken into 2 arrays each with equal average of 12
Array can be broken into 2 arrays each with equal average of 36
Array can be broken into 2 arrays each with equal average of 60

Но эти ответы неверны.

Например, когда сумма подмножества = 12, соответствующие элементы будут {11, 1}. Потом:

(11 + 1)/2 != (7 + 15 + 29 + 9)/4

Я что-то неправильно понял здесь?


algorithm knapsack-problem dynamic-programming subset-sum
person user248884    schedule 07.09.2018    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Я что-то неправильно понял здесь?

Кажется, вы это сделали.

Для данного массива среднее всегда равно 12 - общее среднее, среднее по первому подмножеству, среднее по второму подмножеству.

Итак, вы должны проверить:

  • 1-элементное подмножество с суммой 12 - не существует
  • 2-элементное подмножество с суммой 24 - существует 9+15
  • 3-элементное подмножество с суммой 36 - не существует

и нет необходимости проверять большие суммы (>n/2)

person MBo    schedule 07.09.2018
comment
Извините, я до сих пор не понимаю, почему мы должны проверять 1-элемент, 2-элемент и 3 элемента. Не могли бы вы уточнить? - person user248884; 07.09.2018
comment
Потому что это выбранный подход — мы пытаемся построить k-подмножества с ave = subsetsum / k для всех возможных k. На самом деле мы должны проверить только k<= n/2 - person MBo; 08.09.2018

arrow_upward
1
arrow_downward

Необходимо указать номер элемента суммы подмножества. Достаточно найти элемент меньше, чем n/2. И есть другие ошибки. Коды, как показано ниже:

bool SubsetSum(vector<int> &A, int number, int Sum)
{
    bool dp[Sum+1][A.size()+1];
    int i, j;
    for(i=0; i<= A.size(); i++)
        for (j = 0; j <= Sum; j++)
            dp[j][i] = false; // When sum = 0
    dp[0][0] = true; // When num = 0 of 0 elements
    for(i = 1; i <= A.size(); i++)
    {
        for(j=Sum; j>=A[i-1]; j--)
        {
            for (int k = A.size(); k > 0; k--)
                dp[j][k] = dp[j][k] || dp[j-A[i-1]][k-1];
        }
    }
    return dp[Sum][number];
}

void avgset(vector<int> &A) {
    int total = accumulate(A.begin(), A.end(), 0); // Cumulative sum of the vector A
    int ntotal = A.size(); // Total number of elements

    int i;
    for(i=1; i<=ntotal/2; i++) // Subset size can be anything between 1 to the number of elements in the total subset
    {
        if((total * i) % ntotal == 0)
        {
            if(SubsetSum(A, i, (total * i)/ntotal)) // Required subset sum = total * i)/ntotal
                cout<<"Array can be broken into 2 arrays each with equal average of "<<(total * i)/ntotal<<endl;
        }
    }
}

вывод:

Array can be broken into 2 arrays each with equal average of 24
person zhiwen    schedule 07.09.2018
comment
Привет, Пожалуйста, помогите мне понять: (1). Что вы подразумеваете под element number of subset sum. (2). Почему вы урезали базовый корпус. то есть: почему только dp[0][0] верно, а не весь столбец. Я думаю, что весь столбец должен быть верным, поскольку, когда мы должны сделать Sum = 0, всегда есть 1 вариант (ничего не выбирайте). (3). Почему вы перевернули второй цикл for for(j=Sum; j>=A[i-1]; j--). (4). Какова цель for (int k = A.size(); k > 0; k--) - person user248884; 07.09.2018
comment
1. Найдите, что k * avg должно совпадать с числом k, поэтому разбиение avg равно (k*avg)/k = avg. 2. Только 0 значение элемента как 0 истинно. другое значение должно быть обработано. 3. не реверс также подходит, убедитесь, что j в [A[i-1], Sum]. 4. k означает количество элементов значения суммы, поэтому можно найти заданное количество элементов, соответствующих значению суммы. - person zhiwen; 08.09.2018