我写了一段code, 不过只是单纯的 recursive traversal而已, 还没用上DP技巧. 所以时间复杂度为O(n!), 不过应有很大的改善空间. 这是用php写的, 可以透过这个网址试run看看: http://bobju.dyndns.org/cuts/form.html 因为只是要验证程式逻辑而已, 所以很多防呆防弊机制都没做, 预计时间 复杂度为O(n!), 所以测试资料请给小量就好, 大量的话恐怕会跑到挂. :P 若有错误, 敬请指教; 若无错误又有需要的话, 欢迎自行修改. <?php $MIN_COST=9999999; $LENGTH=$_REQUEST['length']; $nodes=explode(",",$_REQUEST['nodes']); if(count($nodes)>7){ echo "节点超过7个, 恕不受理"; echo "<a href='http://bobju.dyndns.org/cuts/form.html'>返回</a>"; exit; } //定义节点串列结构: //将所有节点由小到大依序排好, 并指定初值. //每个节点有两项属性需要记录: isCut为true, 代表此节点已被截取, isCut为false, 代表此节点尚未被截取. //cost代表该节点被截取时所产生的成本, 初始值为0. $list=array(); foreach($nodes as $n){ $list[$n]=array('isCut'=>false,'cost'=>0); } //用来记录节点被截取的序列. $ans=array(); // traversal($list,1,$ans); echo "最小总成本: $MIN_COST"; /* 以递回方式列举所有节点被截取之顺序的所有排列情形 * 在列举的过程当中, 计算节点被截取时所产生的成本, 并记录起来. * list为pass by reference的方式传入, 在递回过程中处理的都是同一份记录. * layer代表处理的层数, 同时也代表目前所处理的截点序数. * ans用来记录节点被截取的序列, 也是以pass by reference的方式由外部传入. */ function traversal(&$list,$layer,&$ans){ //用来记录所有traversal路径中的最小总成本. global $MIN_COST; //对於list中的所有节点, 进行以下处理: foreach($list as $k=>&$v){ //若此节点已被截取, 则略过. if($v['isCut']) continue; //若此节点尚未被截取过, 则进行处理: //计算截取成本: $cost=count_cost($list,$k); //将此截点记录起来: array_push($ans,array($k,$cost)); //若目前的处理层数已达到list的所有节点总数, 代表已形成一个完整的截点序列, 进 行以下处理: if($layer==count($list)){ //将结果以特定格式输出 echo nl2br(array_dump($ans,$tcost)); //记录目前最小总成本 $MIN_COST=($tcost<$MIN_COST)?$tcost:$MIN_COST; //输出完毕後, 最近刚处理的截点状态还原成未截取状态. $v['isCut']=false; $v['cost']=0; //将此截点的记录弹掉. array_pop($ans); //返回 return; } //若目前处理层数尚未达到list的所有节点总数, 则: else{ //将此节点标记为'截取' $v['isCut']=true; //继续往下一层进行处理: traversal($list,$layer+1,$ans); //当下层都处理完返回时, 将此截点标记为'未截取' $v['isCut']=false; //将此截点的记录弹掉. array_pop($ans); } } } /* 输出结果 * * */ function array_dump($ans,&$tcost){ $output=''; $tcost=0; foreach($ans as $v){ $output.=sprintf("(%d,%d)",$v[0],$v[1]); $tcost+=$v[1]; } $output.=sprintf(" cost:%5d\n",$tcost); return $output; } /* 计算成本: * 给予一个点座标$k, 计算此点向左(右)量测到最近截点(或边界点)之间的距离和. * $list记录着所有节点目前的截取状态及截取时所产生的成本. * */ function count_cost(&$list,$k){ global $LENGTH; $list[$k]['cost']=0; $left_bound=0; $i=$k-1; while(!$list[$i]['isCut'] && $left_bound<$i){ $i--; } $list[$k]['cost']+=abs($k-$i); $right_bound=$LENGTH; $i=$k+1; while(!$list[$i]['isCut'] && $i<$right_bound){ $i++; } $list[$k]['cost']+=abs($k-$i); return $list[$k]['cost']; } ?> ※ 引述《king19880326 (OK的啦～我都可以接受)》之铭言： : ※ [本文转录自 C_and_CPP 看板] : 作者: king19880326 (OK的啦～我都可以接受) 看板: C_and_CPP : 标题: [问题] 请问有关锯木问题写成程式比较快的方法 : 时间: Mon Apr 27 08:51:15 2009 : 题目叙述如下 : 有一个木头, 长度是 L, 假设位於座标 (0, L)中间, 现给 n 个点 p1, p2...pn : 0 <= pi <= L (1 <= i <= n). 希望可以将原本的木头切成这 n+1 段 : 现在定义切木头的cost如下 : 如果木头长度是 L1, 则切此木头的 cost 就是L1 : (不论切在哪一个点). 试问该用何种顺序才能使得切出这 n+1 段的 cost 为最小 : 举例: : 假设木头位於 (0, 9) 要切的 3 个点 分别为 3, 4, 8 : 则如果由右往左切 cost 为 9(0 -> 9 中切 3 这个位置) + 6(3 -> 9中切 4 这 : 个位置) + 5(4 -> 9中切 8 这个位置) = 20 : 如果是由左往右切 cost 为 9(0 -> 9 中切 8 这个位置) + 8(0 -> 8中切 4 这 : 个位置 + 4(0 -> 4中切 3 这个位置) = 21 : 我的想法如下 : : 定义 P(i,j) 为 (1 <= i <= n, 1 <= j <= n) 为 切第 i 刀时, 所切的位置在 : j 的 cost 最小. : 以下是一个简单的观察 : min{P(n,1), P(P,2), ... P(n,n)} = 所求 : (因为共要切 n 刀, 而第 n-1 刀有可能是切在 p1, p2, ...pn 这 n 种可能) : P(i, j) = min{P(i-1,1) + 切在 j 的代价, P(i-1, 2) 切在 j 的代价, ...P(i-1,n) : + 切在 j 的代价} (令P(i-1,j) = 负无限大) : P(1, j) = L (1 <= j <= n) : 因此用 DP 填表格的方式 共 n * n 格要填 : 填每一格需要的时间复杂度 为 O(n) : 所以时间复杂度是 O(n^3) : 这样的时间复杂度好像有点高 @@>, 请问有什麽方法可以把它的时间复杂度往下降吗?? : 感谢感谢 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 59.104.186.105