征求算法(100分)

X

xieyj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-30

• #1

如下表，假设所有序号对应总的Quantity 之和为 Total_Sum(Quantity)=1000 ，现在要从下表取几个序号出来（个数不固定），
取出来的几个序号要满足条件

（1） 对应取出来的序号的Quantity之 和 sub_sum(quantity) >= Total_Sum(Quantity) * 0.2 ，
（2） 没有任何其他的几个序号对应的和比 sub_sum(quantity) 更小且满足条件（1）
（3） 并且取出来的序号是最少的


No Quantity
1 20
2 16
3 23
4 25
5 10
6 12
7 23
8 32
9 23
10 19
11 17
12 16
13 10
14 20
... ...
50 21

 

X

xieyj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-30

• #2

没人知道吗？

 

P

pyh_jerry

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-30

• #3

怎么有点象玩21点哦

我做过一个图的最佳路径的算法应该和这个类似（让游戏中的精灵能自动找到最佳行进路线）
可以设计一个遍历，先从找最接近 t:=Total_Sum(Quantity) * 0.2 的a数,然后再求一数
b让a+b最接近 t,以此类推.最后必然得到一数组 f,且数据由大到小排列
然后从剩下的数中再找一个最接近 t 的数 k,再从数组 f 中由小到大找边续的 n 个数
使其和大于且最接近于 k；用 k 替换这 n 个数,以此类推，递归执行，直到 n=0

嘿嘿，说起来不容易，做起来更难
[8D]怎么样已经晕了吧，给分给分[]

 

天

天真

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-02-08

• #4

听课！

 

M

mat

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-02-08

• #5

真晕真晕

 

X

xieyj

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-04-09

• #6

接受答案了.