作者walker2009 (谁人未尝自以为)
看板Prob_Solve
标题[问题] 一个感觉是 dynamic programming 的题目
时间Tue Apr 20 14:24:34 2010
※ [本文转录自 C_and_CPP 看板]
作者: walker2009 (谁人未尝自以为) 看板: C_and_CPP
标题: [问题] 一个感觉是 dynamic programming 的题目
时间: Tue Apr 20 14:12:20 2010
朋友问了我一个题目 我感觉是 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: 114.32.236.211
※ 编辑: walker2009 来自: 114.32.236.211 (04/20 14:13)
1F：→ Dannvix:有 prob_solve 板唷 04/20 14:20
2F：→ walker2009:喔喔喔喔! 3q 04/20 14:21
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.32.236.211
3F：→ aks4751:单看问题的话，我觉得这比较像NPC问题(0-1背包问题) 04/20 16:43
4F：→ aks4751:就算存在DP解可能也很慢 04/20 16:45
5F：→ aks4751:我好像搞错了...请删除吧 04/20 17:10
6F：→ walker2009:XD 04/20 18:04
7F：→ walker2009:以最下面那个箱子而言 的确上面感觉像是 0-1背包问题 04/20 18:05
8F：→ walker2009:但以第二个箱子而言 上面又是另外一个 0-1背包问题 04/20 18:05
9F：→ walker2009:提供了我一个思考方向 感恩! 04/20 18:06