CODEWITHSUNDEEP
algorithmdynamic-programmingknapsack-problem
n00bster
n00bster

Reputation: 449

knapsack problem variation with almost no constraints

I have this variation of knapsack with very few constraints, and the lack of contraints does that i really don't know where to start.

Given a set S of positive integers. could be: 1 2 3 4 5 6 7 8 9 10 11 12 13

find two non-overlapping subsets that have the same total each. The two sets do not need to contain all numbers in S. So for the former example, the answer would be [1,2] and [3]

Usually these problems have constraints such as the subsets needing to have specific sums, or the subsets needing to span over all elements of S. This makes it hard for me to imagine how to solve this via bruteforce. Every time I come up with a dynamic programming table, I can't get it to cover all possible permutations of subsets

Upvotes: 2

Views: 164

Answers (1)

MBo
MBo

Reputation: 80187

This problem might be solved like subset sum problem in pseudopolynomial time O(n*summ)

We fill array 0..summ with possible subset sums, and when we meet the same sum - we stop.

Two equal sums might be composed with some equal items - and we just remove them, so the rest sums contain only distinct items.

Example in Python using binary arithmetics to store sets (bit i+1 corresponds to using i-th item in sum). common contains equal bits, we remove them using xor operation.

The last lines retrieve needed sets themselves.

L = [2,5,11,17,29,37,43]
summ = sum(L)
A =[0]*(summ+1)
A[0] = 1

X = 0
Y = 0
for i in range(len(L)):
    for k in range(summ, L[i] - 1, -1):
        if A[k - L[i]]:
            t = A[k - L[i]] | (2 << i)
            if A[k]:
                common = A[k] & t
                X = A[k] ^ common
                Y = t ^ common
                break
            else:
                A[k] = t
    if X:
        break

first = [L[i] for i in range(len(L)) if (X & (2 << i))]
second = [L[i] for i in range(len(L)) if (Y & (2 << i))]
print(first, second)

>>> [2, 11, 29] [5, 37]

In this example code finds equal sums 59 for [2, 11, 17, 29] and [5, 17, 37] and removes common 17 to get final results with sum 42

It is not obligatory to store sets in A[] cells - we can store the last item of sum, then unwind item sequence

L = [2,5,11,17,29,37,43]
summ = sum(L)
A =[0]*(summ+1)
A[0] = -1
last = 0
for i in range(len(L)):
    for k in range(summ, L[i] - 1, -1):
        if A[k - L[i]]:
            t = L[i]
            if A[k]:
                last = k
                break
            else:
                A[k] = t
    if last:
        break

first = set()
k = last
while k:
    first.add(A[k])
    k = k - A[k]

second = set()
second.add(t)
k = last - t
while k:
    second.add(A[k])
    k = k - A[k]

print(first.difference(second),second.difference(first))

>>> {2, 11, 29} {37, 5}

Upvotes: 2

Related Questions