※ 引述《journeyman.bbs@bbs.csie.ncu.edu.tw (㊣維士比啦！)》之銘言：
: > 請教版上各位高手
: > 假設有一個大長方形 ex. 1000x1000
: > 及一些大小不等的小長方形 ex 20x30 50x70 100x300 400x600 ......
: > 有沒有什麼演算法可以判斷這些小長方形是否能完全放到大長方形裡
: 哎呀！這不就是那個"0-1 knapsack"問題嗎？
: 以前聽到這個問題的時候，要用GREED解
:
"0-1 knapsack"算是NPC中比較好解的問題了
通常如果範圍不大的話 可以用DP的方式求解 實際上還有用的
GREEDY是不行的
你說的應該是 "fractional 0-1 knapsack"問題 這就是GREEDY 取單位價值最高的部份
其他蠻多的NPC就沒這麼簡單 用DP也沒辦法
-----
10x10 的大長方形 可以放小的11x1嗎?
其實可以放對角線XD.....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.205.46