[Solved]: How to reduce from subset-sum problem?

Problem Detail: 

I have this problem which is described as follows:

Input: You are given a multi-set $M$ (a set that can contain duplicates), and two numbers $P$ and $T$. $M = {(x_1,y_1), (x_2,y_2), ..., (x_n,y_n)}$. Each $x$ and $y$ is an integer $>= 0$. $P$ in an integer $>= 0$. $T$ is an integer $> 0$.

Question: Is there a subset $G$ of $M$, such that the sum of every $x$ value of $G$ is $> P$ and the sum of every $y$ value of $G$ is $< T$? (Note: You are basically taking from $M$. For example: if $M$ has two $(1,1)$'s then $G$ can contain at most two $(1, 1)$'s)

I want to reduce it to from the subset sum problem, but I am not sure how because there's two conditions to solve for...

Can anyone help with this problem?

Asked By : omega

Answered By : Vor

Suppose that you have an instance of SUBSET SUM:

$0 \leq x_1, x_2, ..., x_n$ and an integer $0 \leq t$

You must find $b_i \in \{0,1\}$ such that $b_1*x_1+b_2*x_2+...+b_n*x_n = t$

Which is equivalent to:
$b_1*x_1+b_2*x_2+...+b_n*x_n \geq t$ AND $b_1*x_1+b_2*x_2+...+b_n*x_n \leq t$

$b_1*x_1+b_2*x_2+...+b_n*x_n > t-1$ AND $b_1*x_1+b_2*x_2+...+b_n*x_n < t+1$

pick $P=t-1$, $T=t+1$, $M = \{ (x1,x1),....,(x_n,x_n)\}$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10747