Reduction from Subset Sum

Vote count:

0

trying to wrap my head around this one reduction problem.

Basically, given n amount of lists M, each consisting of {x1, x2...xn}{y1, y2...yn}, where each xi is linked with the corresponding yi, is there a list S = {(x1,y1),(x2,y2)....(xn,yn)} such that the sum of all x'es is atleast T, and the sum of all y at least W (or as large as possible?)

Basically you get to pick 1 tuple from each list and create a set of the same length as M, but with tuples instead of lists if you will. The y variables are tied to the corresponding x variables.

This problem is supposedly reducible from the known Subset-sum problem.

Do I need to combine two separate sub-set sum solutions in order to make this work? For example applying subset sum first to a subset S of x'es, checking that this subset is at least T, and then using this subset to check the corresponding y variables and verifying that their sum is at least W?

Any help would be greatly appreciated, will explain in more detail if asked.

asked 28 secs ago

D. Giver

3

Reduction from Subset Sum