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)}$
$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
