hur.cn - 华软网

 热门搜索

求最佳算法!!(高分)!!!

  作者:未知    来源:网络    更新时间:2018/8/6
有一个二维数组A(m,6)
其中A(n,1)~A(n,6)的值,形式为:

23,43,35,0,0,0 或
77,33,0,0,0,0 或
55,22,56,88,44,98 或
556,111,667,888,435,0 或
…………

也就是说同一行中末几列数值可能为0,最多4个0,最少没有,前面至少2位都是正数,行数不限。

还有一个一维数组B(f)   
其中每一个值都大于A中任意数值
行数不限






现在给出另一个结构数组:
C(g)

C的结构为
{
max //最大值
min //最小值
}

max,min 都是正数,相差不大




要求:

给出A,B, C, 要求在A中找出尽量少的几行,用B中任意数值减去其中的数值使符合C的范围,即以最少的行数满足C给出的全部范围。B,C中的行不能重复使用,即已经用来减去A中某一行的B行不能再次减另一行,C中已经满足的一组范围不要再次满足。

列出所有可能。
然后得到相减结果最接近min值的那一组选择。

可能说的不清楚,大家多帮忙。


------华软网友回答------
简单的说,就是给出一组源数据A,再给出一组条件数据B,要求两者相减达到一组取值范围C。

其中A,B都是有冗余的,行数也不同,相减的时候必定为A的一个元素减去B中某一行所有元素得到6个(B行中含0则不足6个)差值,然后和C中某个范围进行比较;

要求:
1. C中每个元素的取值范围必须全部满足,如果最后任何组合都无法满足C中全部范围则提示错误;
2. 如果1可以满足则求出相减使用的B行数(即A行数)最少的组合方式。
------华软网友回复------
我在楼上把A,B说反了,不好意思。
------华软网友回复------
随便写点数据

A(5,6)
7.3,7.4,8.5,8.3,7.5,8.1
2.1,8.4,0  ,0  ,0  ,0
5.4,5.1,5.9,5.5,0  ,0
6.5,6.3,6.1,5.3,7.5,0
8.1,7.2,6.9,8.5,6.7,8.3

B(8)
10.2
9.6
9.8
10.2
10.3
10.1
9.7
9.8

C(7)
4.2~5.1
3.3~4.1
1.5~2
2.3~2.6
3~3.5
4.5~5
3.6~4.3

用B中的某一个值,分别减去A中某一行的每一个值(0不算),得到的差值与C中范围作比较,如果至少有一个差值能满足C中的至少一个范围,则B的这个值和A的这一行暂定为可选,已被满足的C条件(1个或几个)被标记不再用来判断。然后在A,B剩下的行中依此尝试直到C中剩下的所有条件被满足。


显然有很多种排列组合方式。要求选出一种使用A行数最少同时C中所有范围能被差值满足的组合方式。

------华软网友回复------
第一步一定是求C的重叠区间
如:
C(7)
4.2~5.1
3.3~4.1
1.5~2
2.3~2.6
3~3.5
4.5~5
3.6~4.3
————————————————————————
3.6~4.3与4.2~5.1之间有4.2~4.3的重叠区间
3.3~4.1与3.6~4.3之间有3.6~4.1的重叠区间
3.3~4.1与3~3.5之间有3.3~3.5的重叠区间
……
可能还有3个区间同时重叠的,
重叠区间越多的C元素,一一去组合A与B,优先满足
过程是这样, 不过写起来不容易,
还有,也可能是无解.
------华软网友回复------
就是太麻烦了,无助啊~~~~
------华软网友回复------
没有Money,看起来头疼
------华软网友回复------
还是转到算法区去吧,那里有一帮狂人,应该可以搞定的
------华软网友回复------
嘿嘿,俺的脑袋瓜也不好使,再说也懒,
要是非解决这个问题的话,我不会想太多时间,
笨方法写,反正写完了,是计算机在跑,又不是我,
就算非最优解法,在现在PC上跑,一般还是没什么很大差别的,
不管怎么样,先实现目标再说,优化的事情慢慢来吧...
------华软网友回复------
呵呵,顶楼上的
------华软网友回复------
换个最简单的说法,给出二组数据A,B,
A  1   2   3    4   3   4   1   2
B  1.1  1.3  0.9   3.2  5.1  4.5  0.8  2.3  2.4  3.2  4.3  4.6 2.0 

以A为标准从B中选出元素与之配对,要求: 0.5 >=  (A-B) >=0 ,绝对值尽量小,并且A中所有元素都必须得到配对,否则给出提示。

求最佳搭配方式。
------华软网友回复------
decimal a[]={ 1,2 ,  3 ,   4,   3 ,  4 ,  1,   2}
decimal b[]={1.1,1.3,0.9,3.2,5.1,4.5,0.8,2.3,2.4,3.2,4.3,4.6,2.0 }
long la,lb,laa,lbb
decimal tmp1,tmp2

for la=1 to upperbound(a)
tmp1=10000
for lb=1 to upperbound(b)
tmp2=a[la] - b[lb]
if tmp2 >= 0 and tmp2 <= 0.5 then
if tmp1 > tmp2 then
tmp1=tmp2
laa=la
lbb=lb
end if
end if
next
if tmp1 <> 10000 then
lb_1.additem('A['+string(laa)+']-B['+string(lbb )+']='+string(tmp1))
else
lb_1.additem('A['+string(la)+']无配对')
end if
next

------华软网友回复------
啊,被我这么一弄成了简单循环问题,我自己寒一个。
------华软网友回复------
csdsjkk() 有点误解我的意思,不过还是谢谢。我自己先把问题简化再说吧。      
华软声明:本内容来自网络,如有侵犯您版权请来信指出,本站立即删除。