如何从子集问题中减少？

Question

我有这个问题，如下所示：

输入：给您一个多组$ M $（可以包含重复项的套件）和两个数字$ p $和$ t $。 $ m = {（x_1，y_1），（x_2，y_2），...，（x_n，y_n）} $。每个$ x $和$ y $都是整数$> = 0 $。整数中的$ p $ $> = 0 $。 $ t $是整数$> 0 $。

问题：是否有$ m $的子集$ g $，以便每$ x $的总和$ g $是$> p $，每$ y $的总和$ g $ is $ g $ is $ <t $？ （注意：您基本上是从$ m $中获取的。例如：如果$ m $具有两个$（1,1）$，那么$ g $最多可以包含两个$（1，1）$'s）

我想从子集总和问题中将其减少到，但是我不确定如何解决两个条件。

谁能帮助解决这个问题？

Answer 1

假设您有一个子集总和的实例：

$ 0 leq x_1，x_2，...，x_n $和一个整数$ 0 leq t $

您必须找到$ b_i in {0,1 } $，以便$ b_1*x_1+b_2*x_2+...+b_n*x_n = x_n = t $

等同于：
$ b_1*x_1+b_2*x_2+...+b_n*x_n geq t $和$ b_1*x_1+b_2*x_2+...+b_n*x_n*x_n leq t $

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

选择$ p = t-1 $，$ t = t+1 $，$ m = {（x1，x1），....，（x_n，x_n）} $

Answer 2

我认为与该系列的总和相同。
因此，例如，如果有一个$ g_1 $，以便所有x> p的总和（$ g_1 = {（x，y）： sum {x}> p } $），然后set $ g_2 $，使得所有y <t（$ g_2 = {（x，y）的总和sets（$ g = {g_1 bigcap {g_2}} $）。这些集可以更多，具体取决于创建的多种方式的总和。
如果取决于要采取哪个元素，则应是一组集合，以便如果$ g = {g_1 bigcap {g_2}}} = {（x_1，y_1），（x_2，y_2），... ：（ x_1，y_1） space包含 space k_1次，（x_1，y_1） space包含 space k_2 space Times，...} $，然后您可以创建$ K_1K_2K_2K_3 ... $ sets。
我认为这取决于对结果处理的特定需求。
如果$ m = {（1，1），（1,1）} $，$ p = 1 $，$ t = 3 $，然后$ g_1 = {（x，y）： sum {x} > 1 } = m $，$ g_2 = {（x，y）： sum {y} <3 } = m $和$ g = g_1 bigcap {g_2} = m $。
如果$ m = {（1，1），（1,1）} $，$ p = 1 $，$ t = 2 $，然后$ g_1 = {（x，y）： sum {x} > 1 } = m $，$ g_2 = {（x，y）： sum {y} <2 } = {（1,1）} $和$ g = g_1 bigcap {g_2} = {（（ 1,1）} $，如果$ g $包含第一对或第二对，则无关紧要。