荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: Version (Who makes history and why), 信区: Program
标 题: Re: 算法高手接招！
发信站: 荔园晨风BBS站 (Thu Mar 27 14:53:58 2003), 站内信件
easy，典型的动态规划
设m个数为b[1..m] of integer
开数组
a[0..n,-20*n,20*n] of boolean
在特定的k下，a[i,j]表示从第一到第k个数中取i个，是否能得到和j
初态：
fillchar(a,sizeof(a),false);
a[0,0]=true
计算：
for k=1 to m do
for i=1 to n do
for q=-20*i to 20*i do
a[i,q]=a[i,q] or a[i-1,q-b[k]]
最终在a[n,0],a[n,-1],a[n,1],a[n,-2],a[n,2]..中找第一个为真的a[n,p]
|p|为你需要的最小绝对值。
空间复杂度O(n^2)
时间复杂度O(m*n^2)
【 在 Version (Who makes history and why) 的大作中提到: 】
: 有m个数，m≤200，且每个数在-20和+20之间，从中取出n个数，n≤20，
: 使其和的绝对值最小
--
*
* *
* *
no more to say
★ just wish you ★
good luck
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.1.50]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店