Re: [問題] 長方形與正方形
看板Prob_Solve (計算數學 Problem Solving)作者march20時間18年前 (2006/11/14 05:23)推噓0(0推 0噓 1→)留言1則, 1人參與討論串6/15 (看更多)
先來大膽假設一件事:
在所有最佳解中, 至少有一個是符合這個 pattern
┌───┬───┐
│ │ │
│ A │ B │
│ │ │
├───┴───┤
│ │
│ C │
│ │
└───────┘
其中 A 為正方型, B 和 C 為矩型 (可能為正方型, 也可能為長或寬為 0 的退化矩型)
如果是這樣, 就可以用 DP 解了:
令原題矩型 width 為 w, height 為 h
求出所有 m x n 矩型的最佳解 S(m, n) // where 0<=m<=w, 0<=n<=h, m<n
(m x n 跟 n x m 意義相同, 限定 m < n || n < m 可以省掉一半的 case)
然後找出最小的 A,B,C 組合, 使得 S(mB, nB) + S(mC, nC) 最小.
不過得先證明以上假設正確 (逃)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 128.54.43.37
※ 編輯: march20 來自: 128.54.43.37 (11/14 05:36)
※ 編輯: march20 來自: 128.54.43.37 (11/14 05:38)
※ 編輯: march20 來自: 128.54.43.37 (11/14 05:39)
→
11/15 15:34, , 1F
11/15 15:34, 1F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
