作者justdemon (人生的转捩点)
看板C_and_CPP
标题Re: [问题] 一个感觉是 dynamic programming 的题目
时间Tue Apr 20 16:54:27 2010
提供小弟思考之後的浅见 有错烦请指教
1. 建一个list 照重量排序
2. 把载重最大的放最下面
3. 把重量在可容许的最大载重以下的最重的箱子放上，并更新剩余容许载重
4. 直到无法在放上任何箱子，纪录最高层数，并取下最上层的箱子，再放上
次重的箱子，直到无法继续，再次纪录层数。(一直递回...)
※ 引述《walker2009 (谁人未尝自以为)》之铭言：
: 朋友问了我一个题目 我感觉是 dynamic programming
: 但又不太确定 (因为我找不到最後的解跟 subproblem 之间的关系 Q_Q)
: 题目是这样的:
: 给定 n 个箱子, 每个箱子有其自己的 重量 以及 载重量
: 现在要将箱子一层一层往上叠, 顺序不拘
: 每个箱子上方所有的重量加起来不能超过自己的载重量
: 试问, 最高可以叠到几层?
: 我一开始想法是, 最大载重量的放最下层
: 之後第 k 层 会选择 下面 k-1 个箱子中
: min(剩余载重量最大的那一个 - 第i个箱子的重量, 第i个箱子的载重量) 最大的那个
: for all i = 1 to n and i'th box has not been used
: 但後来 verify 发现这想法有错误, 而且感觉好像有点偏 greedy
: 每次想 dp 的题目我都会不自觉往 greedy 那边想过去
: 不知道该如何培养对 dp 的敏锐度 Orz 希望有概念的大大能指导一下
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.101.114
1F：推 walker2009:感谢回应, 但经过思考, 把载重量最大的放最下面这一步 04/20 17:02
2F：→ walker2009:似乎就已经不正确了 04/20 17:02
3F：→ walker2009:试考虑两个箱子 一个载重量最大 另外一个只比他少1 04/20 17:03
4F：→ walker2009:但载重量最大的那个很轻, 另外一个非常重 04/20 17:03
5F：→ walker2009:如果把载重量最大的放最下面 非常重的那个就得放上面 04/20 17:04
6F：→ walker2009:使得之後的载重量变得非常小 04/20 17:04
7F：→ justdemon:原题意看起来 载重量不包含自己吧?? 04/20 17:21
8F：→ justdemon:如果包含自己 那最多就是多一层递回 第一层无法直接 04/20 17:22
9F：→ justdemon:决定 应该还可以延用 04/20 17:22
10F：推 walker2009:包不包含其实可以很轻松转换,但不管包不包含应该都无法 04/20 17:27
11F：→ walker2009:直接决定第一层 04/20 17:27
12F：→ mantour:这篇的方法等於把所有允许叠法试过一遍了吧 04/20 17:58
13F：推 walker2009:似乎是XD 时间上应该过不了 04/20 17:59
14F：→ walker2009:依然想不到跟 subproblem 之间的关系...好闷 04/20 18:00
15F：→ walker2009:是说也还没确定是 DP 解啦...搞不好有更好的解法 04/20 18:00