我有这个问题,如下所示:

输入:给您一个多组$ 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)

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

谁能帮助解决这个问题?

有帮助吗?

解决方案

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

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

其他提示

我认为与该系列的总和相同。
因此,例如,如果有一个$ 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 $包含第一对或第二对,则无关紧要。

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top