Subset sum problem, break ties by initial ordering

Question

Given a set of numbers, find the subset s.t. the sum of all numbers in the subset is equal to N. Break ties between all feasible subsets by the initial order of their elements. Assume that the numbers are integers, and there exists such subset that perfectly sums up to N.

For example, given an array [2, 5, 1, 3, 4, 5] and N = 6, the output needs to be {2, 1, 3}. Although {5, 1}, {2, 4} and {1, 5} are also subsets whose total sums up to 6, we need to return {2, 1, 3} according to the ordering of the numbers in the array.

For the classic problem I know how to do it with dynamic programming but to break ties I can't think of a better approach besides finding ALL possible subsets first and then choosing the one with the best ordering. Any ideas?

Think about how we would go about reconstructing the list elements that make up the target sum, and how we might tweak the process to store relevant data. — גלעד ברקן

Francisco Geiman Francisco Geiman · Accepted Answer · 2019-10-09T18:00:06

I will try to provide an interesting way of breaking ties. Let's assign another value to the items, let the value of the i_th item be called v[i].

Let there T items, the i-th item will have $v[i]$ = $2^{i - 1}$ , weight = $w[i]$ .

Among all the subsets of maximum weight, we will look for the one that has the maximum accumulated value of the items. I have set the values as powers of two so as to guarantee that an item that comes first in the array is prioritized over all it's successors.

Here is a practical example:

Consider N = 8, as the limit weight that we have.

Items {8, 4, 2, 2}

Values {8, 4, 2, 1}

We will have two distinct subsets that have weight sum = 8, {8} and {4, 2, 2}. But the first has accumulated value = 8, and the other one has accumulated_value = 7, so we will choose {8} over {4, 2, 2}.

The idea now is to formulate a dynamic programming that takes into account the total value.

$DP[i][W]$ = maximum accumulated value of among all subset of items from the interval [0, i] that have total weight = W.

I will give a pseudocode for the solution

Set all DP[i][j] = -infinity

DP[0][0] = 0

for(int weight = 0; weight <= N; ++weight ) 
{
    for(int item = 0; item < T; ++item ) 
    {
        DP[item][weight] = DP[item - 1][weight]; // not using the current item
        if( v[item] < weight ) continue;
        else 
        {
            DP[item][weight] = max( DP[item][weight], DP[item - 1][ weight - w[item]] + v[item])
        }
    }
}

How to recover the items is really trivial after running the algorithm. DP[T][N] will be a sum of powers of two (or -infinity if it is not possible to select items that sum up to N) and the i-th item belongs to the answer if and only if, (DP[T][N] & v[i]) == v[i].

Subset sum problem, break ties by initial ordering

1 Answers