※ 引述《sustainer123 (caster )》之銘言：
: ※ 引述《oin1104 (是oin的說)》之銘言：
: : 題目翻譯：
: : 有一堆書 給你他們的寬跟高
: : 跟一個寬shelfWidth的書架
: : 每次放書都要照順序垂直放進去
: : 不可以疊在一起
: : 放滿了就放個隔板 然後去下一層放
: : 請問最少要多少高度的書架才能裝下所有書
: : 思路：
: : 我原本沒看到要找順序
: : 所以就sort然後從大賽到小
: : 幹咧
如果沒要求順序的話是 NP-complete
給定一個陣列 A[1..n]
把 shelfWidth 設為 sum(A[1..n])/2
且 n 本書的高度都設 1、寬度是 A[i]
則答案是 2 若且唯若存在 subset 的和恰等於 shelfWidth
所以可以 reduce 成 partition problem
不過 constraint 裡 shelfWidth 最大只有 1000 就是了
:)