作者nicknick0630 (NICK)
看板Prob_Solve
标题[问题] 乌龟塔问题
时间Thu Mar 7 23:40:47 2019
乌龟塔问题 :
有 N 只乌龟，第 i 只重 Wi 克且有 Si 的力量，代表他可以负载 Si - Wi 的重量在背
上
求由这 N 只乌龟可以叠出的最大高度?
我所知道的有 2 种解法
其中一种是用动态规划，解法是 :
先对乌龟用力量由小至大去排序，然後用转移方程式
dp[i][k] = min{ dp[i-1][k], dp[i][k - 1] + Wi }
去算出答案 ( 当然 dp[i][k-1] + Wi 必须 <= Si 才是合法状态 )
上面方程式意思是 "从前 i 只乌龟中，建构 k 层塔的最小重量"
若无法建构 k 层塔则状态为 invalid
我的问题是
为甚麽要对力量去排序? 而不能用重量去排序再做动态规划?
我思考过後，对於重量排序我可以找到反例说明他是错误的
因为重量大的不一样要在重量小的下层
举个例子 :
编号 1 2 3 4
重量 10 20 20 140
力量 60 20 40 150
这样所可以叠出的最大高度为 2 ( 上到下 : 2 -> 3 )
但其实若是用力量去做排序
编号 1 2 3 4
重量 20 20 10 140
力量 20 40 60 150
这样所可以叠出的最大高度为 3 ( 上到下 : 1 -> 2 -> 3 )
所以这样大概可以说明为甚麽重量排序是不对的
因为重量大的可以在上层
那麽我现在所苦恼的就是
为甚麽用力量排序就会是对的?
会不会有个例子是力量小的在上面结果可以让塔更高呢?
请教各位大大了QQ
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.117.183.79
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1551973250.A.28D.html
1F：推 c910335: 单纯好奇你说的两种解法的另一种是这个吗 #1BqHom5S03/08 02:39
2F：→ nicknick0630: 对的哦03/08 09:43
8 09:43
4F：→ nicknick0630: 我有文章是说明这个 Moore-Hodgson 演算法和用他解03/08 09:43
5F：→ nicknick0630: 乌龟塔03/08 09:43
※ 编辑: nicknick0630 (101.15.225.66), 03/08/2019 09:44:34
6F：推 cutekid: 大推 Blog ,写的真好(Y) 03/08 11:24