MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » 两道关于动态规划的题目。本人愚钝实在想不出解法解

两道关于动态规划的题目。本人愚钝实在想不出解法解决方法

www.MyException.Cn  网友分享于:2013-04-27  浏览:7次
两道关于动态规划的题目。。。本人愚钝实在想不出解法
1.(这题本来是关于用限制酶切割DNA的。避免麻烦我去除了生物方面的部分。。说简单一点了。。)
在一条链上有n个节点,其中有一部分是关键点,有一种切割器能截取这条链上任意两个节点之间的一段,现在总共有m种这样的切割器。问题是要求最多用k次切割器(k<m)来截到最大数量的关键点。 比如说,切割器i能切割ai到bi中间的一段,并且某关键点j在这一段上,我们就可以说这个点j被截到了。
总结一下,input是:总节点数n,切割器总数量m,可以使用切割器次数k,关键点的集合(是{1,...,n}的一个子集,但是并没有具体给出),每一种切割器(i=1,...,m)所能切割的两个端点ai,bi
目的是:从m种切割器里选k种,来使截到的关键点数量最大化,要求线性时间。不需要给出最后截出的关键点集合,只需要数量。


2.这题暂且叫他搬运工问题吧。
说是总共有n个位置点,一辆运货卡车停在位置0,其他每个点i都有一个重量为wi>0的大箱子,要把这些箱子按照位置点的顺序从下往上堆在卡车上。由于一个一个搬太费时间精力,所以要找出一个好办法。 假设把重量为w的箱子从a点搬到b点的cost是 c(x,y,w), 当w>w'的时候,c(x,y,w)>c(x,y,w'), 三角不等式也成立:c(x,y,w)+c(y,z,w)>=c(x,z,w)。可以一次抱着几个箱子走。不抱箱子的时候可任意行走于各个位置点不用cost。
由于不能把堆好的箱子重新排序,所以只有相邻的两个箱子可以堆一起,但是每个位置点可以放无限堆,比如说箱子3可以堆到箱子2上,但是如果要把箱子3拿到位置点1,就只能放在箱子1边上而不能堆叠。另外c(x,y,w1)+c(x,y,w2)不等于c(x,y,w1+w2),注意,不等于。 要求就是在cost最小的情况下把所有箱子按照他们所在位置的顺序从下往上堆在卡车上,只要求出cost,具体路线不需要。

哪位能给我点思路。。。谢谢了。。。

------解决方案--------------------
第二题还没看明白,只说第一题吧!

第一题:每个切割器可以多次使用么?否则这个K个几乎没有意义!并且应该做不到线性时间,怎么也需要排个序。如果只能用1次的话,应该用不上DP,有两个思路,1、肯定可以转为二分图匹配问题,肯定可以求得正确的解。2、用贪心,把关键点和切割区间排序后,从左到右扫描,每扫到一个点,尽量选用可以切割该点,并且切割的结束区间靠前的切割器来切割该点,这样应该是可以的,没有太仔细想。
------解决方案--------------------
问题1线性不可能吧,直观复杂度为O(knlogn),斜率优化应该可以优化到O(nk)(猜测),状态就是dp[i][j]表示位置到i用了j次切割的最优。
问题2本质就是石子合并,dp[i][j]来描述区间问题,且该区间性质满足四边形法则,可以优化到O(n^2),有左偏树可以优化到O(nlogn)

文章评论

5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
我的丈夫是个程序员
我的丈夫是个程序员
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
那些争议最大的编程观点
那些争议最大的编程观点
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
代码女神横空出世
代码女神横空出世
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序员和编码员之间的区别
程序员和编码员之间的区别
中美印日四国程序员比较
中美印日四国程序员比较
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
程序员应该关注的一些事儿
程序员应该关注的一些事儿
 程序员的样子
程序员的样子
如何成为一名黑客
如何成为一名黑客
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
每天工作4小时的程序员
每天工作4小时的程序员
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
鲜为人知的编程真相
鲜为人知的编程真相
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
漫画:程序员的工作
漫画:程序员的工作
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
编程语言是女人
编程语言是女人
老程序员的下场
老程序员的下场
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
10个调试和排错的小建议
10个调试和排错的小建议
程序员必看的十大电影
程序员必看的十大电影
旅行,写作,编程
旅行,写作,编程
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
Java程序员必看电影
Java程序员必看电影
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
程序员的鄙视链
程序员的鄙视链
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
为什么程序员都是夜猫子
为什么程序员都是夜猫子
总结2014中国互联网十大段子
总结2014中国互联网十大段子
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有