Как работает это решение задачи о подмножестве сумм?

Это решение проблемы подмножества сумм. Он использует возврат. Я думал об этом более 2 часов, и я просто не могу этого понять.

редактировать: я добавил несколько комментариев к коду на основе того, что я понял. Пожалуйста, поправьте меня, если я ошибаюсь.

#include <iostream>

int n, d, w[10], x[10], count=0;

void subset(int cs, int k, int r)//i dont understand the purpose of cs or of the array x[] 
{
    int i;
    x[k] = 1;

    if(cs + w[k] == d)      //if the first element is equivalent to the sum that is required 
    {
        std::cout<< "\n\nSolution " << ++count << " is:"; 
        for(i=0; i<=k; i++)  // so if the subset criteria are met then the array is printed.
        if(x[i] == 1) 
            std::cout << w[i] << " ";
    }
    else if(cs + w[k] + w[k+1] <= d) //if the node is promising then go to the next node and              
        subset(cs + w[k], k+1, r - w[k]); //check if subset criteria are met

    if(cs + w[k+1] <= d && cs + r - w[k] >= d) //else backtrack
    {
        x[k] = 0;
        subset(cs, k+1, r-w[k]);
    }
}

int main()
{
    int sum=0, i;

    std::cout << "enter n\n";
    std::cin >> n;

    std::cout < <"enter " << n << " elements\n";
    for(i=0; i<n; i++)
        std::cin >> w[i];

    for(i=0; i<n; i++)
        sum += w[i];

    std::cout << "enter value of sum\n";
    std::cin >> d;

    if(sum < d)
        std::cout<<"INVALID SOLUTION\n";
    else
        subset(0,0,sum);

}

Примечание: это рабочее решение. Работает при компиляции с g++. Я извиняюсь, если это кажется слишком неприятным, но я просто мало что понял из кода и, следовательно, не могу дать много объяснений.

Источник

3 ответа

Решение

cs - сумма значений выбранных весов, а r - остаток от суммированных значений весов, которые еще предстоит выбрать. w[i] - вес i, x[i] равен 1, когда выбран вес [i]. В методе подмножества есть две основные ветви решений:

Вес k выбран:

// adding value of weight k to computed sum (cs) gives required sum, solution found
if(cs+w[k]==d)
{
cout<<"\n\nSolution "<<++count<<" is:";
for(i=0;i<=k;i++)
    if(x[i]==1)
    cout<<w[i]<<" ";
}

// both weight k and weight k+1 can be chosen without exceeding d, 
// so we choose k, and see if there's a solution for weight k+1 onwards
// note that available weight values decreased from r to r-w[k]
else if(cs+w[k]+w[k+1]<=d)
    subset(cs+w[k],k+1,r-w[k]);

Вес k не выбран (обратите внимание, что это исследуется, даже если решение было найдено сразу после выбора веса k):

// weight k+1 is choosable (does not exceed d), and despite not choosing weight k
// there would be sufficient weights in r less w[k], and together with the chosen 
// pool cs to meet the requirement of d.
if(cs+w[k+1]<=d && cs+r-w[k]>=d)
{
x[k]=0;
subset(cs,k+1,r-w[k]);
}
Источник

Попробуй это.

#include<iostream>

int n,d,w[10],used[10],count=0;
int cs = 0; // cs=Current Sum

void subset(int k)
{
    if (k >= n) return;  // boundry check
    int i;
    used[k] = 1; // use element k
    cs += w[k];

    if(cs == d) {
        cout<<"\n\nSolution " << ++count << " is:"; 
        for(i=0;i <= k;i++)  
            if(used[i]==1) 
                cout<<w[i]<<" ";
    }
    if (cs < d)  // only when current sum is not enough
        subset(k + 1); 

    used[k] = 0; // not use element k
    cs -= w[k];
    subset(k+1);
}

void main()
{
    int sum=0,i;

    cout<<"enter n\n";
    cin>>n;

    cout<<"enter "<<n<<" elements\n";
    for(i=0;i<n;i++)
    cin>>w[i];

    for(i=0;i<n;i++)
    sum+=w[i];

    cout<<"enter value of sum\n";
    cin>>d;
    cs = 0;
    if(sum<d)
        cout<<"INVALID SOLUTION\n";
    else
        subset(0);
}
Источник

cs - текущая сумма, а x[] - массив, в котором установлено 1 для тех элементов, которые принадлежат ветви решения, которая в данный момент исследуется.

Источник
Другие вопросы по тегам