Subset Sum Problem

a special case of 0/1 KS. (배낭 문제와 비슷)

 

S = {item1, item2, ..., item_n}

weight = {weight1, weight2, ..., weight_}

W: fixed weight (Given)

-> Find A (a subset of S) such that sum of weights in A

    equals W.

 

 

Example: |S| = 5, n = 5. weight_i={5,6,10,11,16}, W=21kg.

solution: {i1,i2,i3}, {i1,i5}, {i3,i4} => multiple solutions

 

algorithms design? -> Brute-force.

All enumerations of possible subsets. -> for-loops << DFS.

DFS하면서 node가 non-promising하면 backtracking

---

Design:

step1. promising function 설계

1) i-th level: weight + weight(i+1) > W.

2) weight + 미래 총 weight 합 < W.

===>IF condition, the STOP.

step2. DFS traverse/visit.

 

#include <iostream>
#include<cstdlib>
using namespace std;

#define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))
static int total_nodes; // 총 생성된 노드

// prints subset found
void printSubset(int A[], int size)
{
    for (int i = 0; i < size; i++)
    {
        cout << " " << A[i];
    }
    cout << "\n";
}

int comparator(const void* pLhs, const void* pRhs)
{
    int* lhs = (int*)pLhs;
    int* rhs = (int*)pRhs;
    return *lhs > *rhs;
}


void subset_sum(int s[], int t[],
    int s_size, int t_size,
    int sum, int ite,
    int const target_sum)
{
    total_nodes++;

    if (target_sum == sum)
    {
        printSubset(t, t_size);
        if (ite + 1 < s_size && sum - s[ite] + s[ite + 1] <= target_sum)
        {
            subset_sum(s, t, s_size, t_size - 1, sum - s[ite], ite + 1, target_sum);
        }
        return;
    }
    else
    {
        if (ite < s_size && sum + s[ite] <= target_sum)
        {
            for (int i = ite; i < s_size; i++)
            {
                t[t_size] = s[i];
                if (sum + s[i] <= target_sum)
                {
                    subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
                }
            }
        }
    }
}

void generateSubsets(int s[], int size, int target_sum)
{
    int* tuplet_vector = (int*)malloc(size * sizeof(int));
    int total = 0;

    qsort(s, size, sizeof(int), &comparator);   // 오름차순 정렬
    for (int i = 0; i < size; i++)
    {
        total += s[i];
    }
    if (s[0] <= target_sum && total >= target_sum)
    {
        subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);
    }
    free(tuplet_vector);
}

int main()
{
    int weights[] = { 15, 22, 14, 26, 32, 9, 16, 8 };
    int target = 53;
    int size = ARRAYSIZE(weights);
    generateSubsets(weights, size, target);
    cout << "Nodes generated " << total_nodes;
    return 0;
}

function promising(i: index)

{

    return (Boolean:T/F) promising =1) and 2) 조건 위배여부.

}

promising function = 수학적 표현.-> T or F return.

 

Analysis:

1. optimal solution generated.

2. Execution time: timer. depending on promising functions.

3. 실세 생성된 노드 수 = 15/31(total) : performance gain.

=> 또는 생성된 leaf 노드 수 / 전체 leaf 노드 수 계산.

 

Questions

: 앞선 예제는 item -> sorted.

1) item들이 역순으로 정렬되어 있었다면?

2) item들이 random 입력되었다면?

 

만약에 정렬하는 것이 우수하다면?

--> 정렬은 전처리로 처리될 수 있다.

---> 전처리가 시간이 다소 걸리더라도, 진행하고 backtracking을 수행하는 것이 좋은것인가?