求一类似24的算法，但比它复杂多了。 (100分)

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-26

• #1

给出一指定的数A,一批随机的数据B1,B2,B3....(Bi<=A)，然后你拿它的任意一个或几个相加之和，这个和要小于或等于A，然后再计算每一个和与A的差，使得所有差的和最小。
如 A=60,B1=2,B2=12,B3=54,B4=21,B5=12.....

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-26

• #2

24点算法，可以用+-*/()[]等，这个呢，只用+法，但这个到底是几个相加，谁也不知，而24点却固定是4个数运算的。

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-26

• #3

没有朋友懂？？

 

Y

yostgxf

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-26

• #4

真的看不明白。
1.随机的数据怎么产生？能不能相同？是整性数？
2.任意一个或几个相加,如果A＝10000，B都为1？
3.什么叫‘所有差的和’

 

我

我就是一个问题

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-26

• #5

这样的算法是不是可以成为背包算法啊!(对不起我实在不是太懂).不过可以说明的是IPB的NO.2的CRACKME其中有一部分算法用的就是这个.没有什么太好的办法解决,不过穷举应该可以解决吧!

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-26

• #6

to yostgxf:
1、随机数可以手工录入，也可以程序产生，只要<=A就行，Bi可以是整数也可以是小数。也可以相同。
2、有这个可能啊。那就是1+1+1+1+1+1....<=1000
3、比如，B1+B2=50,B1+B4=30 ,A=60,那么，所有差的和就是：（60-30）+（60-30），设这个值为N，现在要求这么多组合中，这个N最小的一种组合。

 

H

HorkyChen

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-26

• #7

设A=?,B[?],及一个记录方案的变量Res(最好是字串)和一个记录最小值的值MIN.
主要有两个过程:
先符Min一个极大值,这个不用说吧
Step 1.定义一个函数FunA,找出所有任意数相加小于A的组合结果
Step 2.找出组合状况后,在函数FunB中求出与A的差之和,返回
Step 3.与前面所得比较,下面就可以解决了!
这是最笨的方法.
也可以用贪婪算法,这个就是FunA要实现的细节.例如下面所述:
1.先排序
2.将小于A/2及大于A/2的分隔序号记着,如Index
3.最大加最小,以保证每次尽可与A差异最小
4.找出结果,进入FunB验证

 

H

HorkyChen

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-26

• #8

穷举算法最为简单,易于实现.至于如何找到所有组合,可以看一下树搜索的算法!上面Res的用处在于存放所得到组合的内容!

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-26

• #9

我原来也有个想法，跟HorkyChen大侠的有点相同：
1、排序，用快速法，这个已写好了。
2、取MAX,如果=A，即减去这个数，原数组COUNT-1；
3、最余下的最大+次大，为的就是 HorkyChen 的"以保证每次尽可与A差异最小"；
如果这个和>A，则再取次次大，直到<A则减去这两个数；
4、再回到3。
》》》》以上算法不能保证 次大 这个位置的准确，因为有可能同个次大相加，比单单一个次大更节约。

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-27

• #10

改错：
几
》》》以上算法不能保证 次大 这个位置的准确，因为有可能同个次大相加，比单单一个次大更节约。 ^^

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-27

• #11

改错：
几
》》》以上算法不能保证 次大 这个位置的准确，因为有可能同个次大相加，比单单一
个次大更节约。 ^^

 

H

HorkyChen

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-27

• #12

这是因你设想从大处加起,从大加起没错,我刚才讲最大加最小,同样意指大数如Stone,小的数则为砂粒.像这种组合类的问题,妄谈一句,重点是在于节约遍历时间,不可能用单一模型解决.一旦用一个最字,就是加了一个约束,就可能丢失可能解或最优解.所以可以确立先排序再加的算法可以简化,那么第二步的重点应在于如何遍历才有效率.所以你的第3步只是成了一个组合,程序还应继续求其它组合相比较,从而找出最佳解.

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-27

• #13

昨晚我又在床上想了很久，觉得关键是第3步，本来以为我这样的没问题，但还是有很大的问题，关键是并不能保证需计算差的次数最少，如以下数字：
A=60 B1=30,B2=21,B3=10,B4=10,B5=10,其最佳的组合，应是，30+10+10+10，21，这样，就只"浪费" 60-21=39，若是30+21，10+10+10，虽然最后的差的和也是39（9+30），但需这两个数是从两个A中得到的，并不能为以后若有一个为>30 and <=39所利用，那这就是浪费了。
请HORKYCHEN等大侠们再提提思路。

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-27

• #14

我现在又想到个点点了，在第3步是用走迷宫的方法，遍历所有可能的组合。。。。

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-27

• #15

没有朋友有想法了？？？

 

K

ka_lee

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-27

• #16

“ 3、比如，[red]B1[/red]+B2=50,[blue]B1[/blue]+B4=30 ,A=60,那么，所有差的和就是：（60-30）+（60-30），设这个值为N，现在要求这么多组合中，这个N最小的一种组合。”
我想问那些数中可以重复使用吗？

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-02-27

• #17

to ka_lee
这些数字不能重复使用啊。