求教一个code思路,重新描述一下问题

f
ftmit
楼主 (未名空间)

问题如下:
(1),现有4个条件,i1,i2,i3,i4
(2),这4个条件的全组合计算结果如下:
(2.1),取两两组合(请注意:有的是大于关系,有的是小于关系,a1,a2,a3,a4,a5的值是和f1,f2,f3,f4函数相关的,在这里,您就把他们看作是个数值就可以了)
f1(i1)+f2(i2) .gt. a1
f1(i1)+f3(i3) .gt. a2
f1(i1)+f4(i4) .lt. a3
f2(i2)+f3(i3) .gt. a4
f2(i2)+f4(i4) .lt. a5
f3(i3)+f4(i4) .gt. a6
(2.2),取三三组合(请注意:也存在有的是大于关系,有的是小于关系)
f1(i1)+f2(i2)+f3(i3) .gt. b1
f1(i1)+f2(i2)+f4(i4) .lt. b2
f1(i1)+f3(i3)+f4(i4) .lt. b3
f1(i2)+f2(i3)+f3(i4) .gt. b4
(2.3),取四个组合得出
f1(i1)+f2(i2)+f3(i3)+f4(i4) .gt. c1

问题:4个条件的全组合得出的大于和小于是不一致的(例如:两两组合中,有的是大
于关系,有的是小于关系)

求一个思路,在i1,i2,i3,i4这四个条件中,快速找出哪几个条件的全组合可以得到一
致的大于或者小于关系,例如:找出i1,i2,i3这三个条件,其全组合满足:
(1),取两两组合有(请注意:全都是大于关系)
f1(i1)+f2(i2) .gt. a1
f1(i1)+f3(i3) .gt. a2
f2(i2)+f3(i3) .gt. a4
(2),取三三组合有(请注意:全都是大于关系)
f1(i1)+f2(i2)+f3(i3) .gt. b1

另:这里为了说清楚问题,把条件简化为4个,实际的条件太多了,俺实在没法一组组
去试。

请各路大神指点迷津!多谢了。

B
BroPingtou

先分两类gt lt,作为set of tuples

在每一类里面,从最长的链开始每次去掉一个条件dfs

或者对于任意一组条件组成的tuple,把所有组合都撸出来看是不是都在一个集合里面
【 在 ftmit (八戒) 的大作中提到: 】
: 问题如下:
: (1),现有4个条件,i1,i2,i3,i4
: (2),这4个条件的全组合计算结果如下:
: (2.1),取两两组合(请注意:有的是大于关系,有的是小于关系,a1,a2,a3,a4,a5的
: 值是和f1,f2,f3,f4函数相关的,在这里,您就把他们看作是个数值就可以了)
: f1(i1)+f2(i2) .gt. a1
: f1(i1)+f3(i3) .gt. a2
: f1(i1)+f4(i4) .lt. a3
: f2(i2)+f3(i3) .gt. a4
: f2(i2)+f4(i4) .lt. a5
: ...................

f
ftmit

明白了,只有上循环暴力了。再次感谢!

【 在 BroPingtou (ǢŦĦȆȐ) 的大作中提到: 】
: 先分两类gt lt,作为set of tuples
: 在每一类里面,从最长的链开始每次去掉一个条件dfs
: 或者对于任意一组条件组成的tuple,把所有组合都撸出来看是不是都在一个集合里面

z
zeami

八戒加油。不能找个同事写码然后放二作嘛?
皆大欢喜

【 在 ftmit (八戒) 的大作中提到: 】
: 明白了,只有上循环暴力了。再次感谢!

f
ftmit

这事我做不了主,熬吧,啥时候媳妇熬成婆婆就好了

【 在 zeami (贼阿米) 的大作中提到: 】
: 八戒加油。不能找个同事写码然后放二作嘛?
: 皆大欢喜

r
rongrong2009


【 在 BroPingtou (ǢŦĦȆȐ) 的大作中提到: 】
: 先分两类gt lt,作为set of tuples
: 在每一类里面,从最长的链开始每次去掉一个条件dfs
: 或者对于任意一组条件组成的tuple,把所有组合都撸出来看是不是都在一个集合里面

是力寇儿里的题吗?最近也要刷起来