※ 引述《yoco.bbs@bbs.wretch.cc (眠月..)》之銘言：
: ※ 引述《cplusplus.bbs@ptt.cc (永夜)》之銘言：
: > "0-1 knapsack"算是NPC中比較好解的問題了
: > 通常如果範圍不大的話 可以用DP的方式求解 實際上還有用的
: 我能不能請教一下 0-1 knapsack 問題要怎麼應用DP解 @_@？
: 我只知道有用DP解的方法 卻一直不知道是怎麼用上...
: 請教一下概念就好...
一個背包，N個物品。
把物品分類好。
一項一項編號。
接著。
1號可能放入，可能不放入 放入的話空間-1號大小
2號可能放入，可能不放入 放入的話空間-2號大小
......................
建表(表中為目前之價格最高)。
以目前之空間與放入的物品編號當X,Y。
這是一種方法。
另外一種是
以價格來建表
此種做法，一定要型態有限才行。
: > 其他蠻多的NPC就沒這麼簡單 用DP也沒辦法
: > 10x10 的大長方形 可以放小的11x1嗎?
: > 其實可以放對角線XD.....
: 這個問題我以前遇過
: 我連暴力解法都想不出來 ＿/￣|○
這個問題，應該是往左上角塞。
之前好像有在某精華區看到..
不大有印象了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.142.9.234