作者hatasum (我很可爱)
看板C_Sharp
标题[问题] 叠乌龟问题
时间Thu Oct 30 23:05:33 2008
恩...题目很简单 但是我始终想不出来要怎麽用程式写出来...XD
假设每只乌龟都有两个数据 自己的体重 和 自己最多能乘载的重量
现在有100组乌龟 每只乌龟都有编号(0 1 2...99)
去作堆叠
请用程式找出 最多只乌龟的排法(如果最多只乌龟排法有很多种 那就都要列出来)
Output: 最多叠n只 排列顺序为xxxxxxx
=============================================================================
想了很久...XD但是始终找不到逻辑
我之前的一个错误做法，大家可以参考
=========================================================
第一只放"最大乘载量"的乌龟
他的上面那只放"max(第一只乘载量-第二只重量)"的那一只
=========================================================
我用这逻辑去写 也写出来了 但是发现问题一大堆!!!
ex:
假设用这逻辑 我找出编号顺序为 1=>2=>3=>4(也就是编号1是这data中乘载最大的)
假设经过这1234的排列後 最上面现在只能再放15g以下的乌龟
假设编号1体重10g 可载重100g
编号2+3+4 体重80g 但因为乘载关系 4的上面只能再放15g
现在有第5只乌龟 重量15g 可载重90g
Q1: 1234 这时候也有另一个选择了 5234 (最大乘载量放第一个不一定对了!!)
Q2:
选择1234 4的上面只能再放15g 而5重量20g 所以不能放
选择5234 4的上面只能再放10g 但是1的重量刚好可以放 所以就变成 52341.....
ANS:一开始的逻辑是错的...= =最下面到底要放谁???
============================================================================
目前我还在想 听说有人想出来了XD
但是我总觉得这题目真的可以做出来吗...??
^^"如果有什麽结果我会再po文的 也欢迎大家想想这题目 讨论看看
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 123.0.217.51
※ 编辑: hatasum 来自: 123.0.217.51 (10/30 23:09)
1F：推 varg:用dfs那种作法应该可吧? 10/31 01:14
2F：推 senjor:用HillClimbing直接爬，至少可以很快找出解 @@ 10/31 09:32
3F：→ hatasum:....其实data有100组.... 10/31 21:54
4F：→ senjor:不如把DATA放到网页上，让大家玩一玩吧 XD 11/01 01:00
5F：推 motai:最下面(第一只)放编号1 体重80 载重100 2.3.4叠在上面3只共 11/03 06:46
6F：→ motai:80 那跌最上面的第5只不是应该20以下吗 你说15以下 11/03 06:47
7F：→ motai:我的第一句的编号1打错 是10 11/03 06:48
8F：→ hatasum:真正的负重是min(排出来後剩余的负重, 最上层的负重) 11/05 00:33
9F：→ hatasum:我这例子是取4的负重是15 所以min(20,15) 11/05 00:33