0

Given a list of n-element lists, A, and a target n-element list, t, find a set of lists, S, in A, whose lists sum up to t.

Summing up lists, here, is the addition of elements at the same position. For example, the sum of [1 2] + [2 3] + [7 5] is [10 10].

Here is an example of the problem:

n = 4

A = [[1 2 3 4] [0 0 1 0] [1 0 0 1] [2 0 0 0] [3 0 0 2] [3 0 0 1] [0 0 0 1]]

t = [4 0 1 3]

Then, we must find S.

S = [[3 0 0 1] [0 0 0 1] [0 0 1 0] [1 0 0 1]]

Notice that we don't need all the sets of lists that add up to t -- we only need one.

This problem may seem similar to the dynamic programming coin change that return an array.

Obviously, this problem can be done in brute force with time complexity of O(2^n) by going over the power set of A. Is there a more optimal solution? Is there another problem similar to this?

oamandawi
  • 405
  • 5
  • 15
  • Im certain there is. BUT we dont do your homework for you. You should sit down and take a good wack at it. Then post your attempt and we can tweak it! :) – Fallenreaper Jan 28 '20 at 02:53
  • @Fallenreaper Thank you for your reply. This is not a homework problem; it's a problem I encountered while working on a side project: https://github.com/Mandawi/ToWear. I'm not sure how to do it in another way. My current non-working solution is in the function findMin, here: https://github.com/Mandawi/ToWear/blob/master/points_to_english.py. – oamandawi Jan 28 '20 at 03:02

1 Answers1

1

Solving your problem is equivalent to solving Subset sum problem, which is NP-complete, so your problem is NP-complete too. It means that your problem can't be solved in polynomial time.

Although, if absolute values of all numbers in your lists are less than M, there is a subset sum problem solution in O(n*M*size(a)) (you just need to modify it to your problem, but it is still exponential relatively to number of bits in numbers and takes a lot of memory, but may be better than brute force in certain cases).

ardenit
  • 3,610
  • 8
  • 16
  • Thanks for clarifying. I forgot about the subset sum problem but I see the similarity. All numbers in my lists are between 0 and 10, N is 4, and the cardinality of A has a limit of 50 for my particular problem. I don't understand how the Pseudo-polynomial time dynamic programming solution for the subset sum relates to this, given I don't have any negative elements. – oamandawi Jan 28 '20 at 03:45
  • If you don't have negative values, then you count the sum of negative values as zero. – ardenit Jan 28 '20 at 04:08
  • I think the wikipedia page you linked references Pisinger's solution. The solution is in O(n) per https://stackoverflow.com/questions/9962568/fast-solution-to-subset-sum-algorithm-by-pisinger. I will try to modify that solution to my problem. Thank you for the help! – oamandawi Jan 28 '20 at 04:21