Pseudo polynomial or fast solution for the multiobjective subset-sum

Question

I am looking for a fast solution for a multiple/multiobjective subset-sum problem.

As aditional restraints (which make a litte easier to calculate IMO) we can assume that all values included in the sum are positive and are all bound to a known limit value.

I know there is a O(NK) pseudopolynomial solution for a one-objective subset sum problem, I have implemented a solution based in wikipedia and in this stack exchange answer.

Explaining this problem in other way, I have two sets of positive numbers which limit is known. For each value A in the first set there is a combination of values in the second set that sums up to A. Knowning a priori that all values in the first set have a corresponding and not conflicting combination of values associated in the second set, is there a known, fast way to calculate which elements in the second set are associated with each of the first set values?

Answer 1

I think your problem is a variation of multiset constraint problem which I studied in my master thesis.

In this project, I designed an algorithm which searches in the DP table to find the solution. It is not Pseudo polynomial but I think it is fast enough in general cases.

I also implement a Python tool to solve these problems. Maybe you want to try it !

This tool called msat and it is maintained on github.

You can reference to msat.

Or simply use pip to install it(it is a Python3 tool):

$ pip install msat

There are also slides of introduction: slides.

If you want to know the details, reference to thesis.