作者operationcow (香蕉公車)
站內C_and_CPP
標題[問題] 請問背包問題寫成程式有沒有比較好的方法
時間Sun Apr 5 04:02:37 2009
※ [本文轉錄自 Prob_Solve 看板]
作者: operationcow (香蕉公車) 看板: Prob_Solve
標題: [問題] 請問背包問題寫成程式有沒有比較好的方法
時間: Sun Apr 5 04:00:21 2009
小弟我最近遇到了背包問題
題目敘述如下:
現有一背包可負載的重量為k, 有編號1 ~ n種物品,重量分別為 k1, k2...kn
ps. 每一種物品可使用的數目不限
每一種物品有各自的價值, 分別為 v1, v2, ... vn
請問是否存在一種裝法, 可以把背包的重量k裝滿, 且價值為最大
小弟我目前的想法如下
令原問題(背包重量k, n種物品)的解為 p(n,k)
則若我可以知道p(n, k-k1), p(n,k-k2), p(n, k-k3)...p(n,k-kn)
則p(n,k) = max { p(n,k-k1) + v1, p(n,k-k2) + v2,...p(n,k-kn) + vn} -(1)
原因是放最後一個物品的時候,可能的來源有: 最後一個是編號1的物品,最後一個
是編號2的物品...最後一個是編號n的物品
因為有(1)這個關係式,所以我使用DP填一個n * k的表格
又因為填每一格需要的時間複雜度為(n)
共n * k個要填, 時間複雜度為(n^2 * k)
請問這個時間複雜度還有辦法往下降嗎？
又該如何做呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.131.228.139
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.131.228.139
※ 編輯: operationcow 來自: 220.131.228.139 (04/05 04:03)
推 netsphere:填每一格需要O(n)好像有點高喔 04/05 09:19
→ operationcow:那應該怎麼做呢??感謝感謝 04/05 09:31
推 netsphere:要是我會從改進遞迴式開始 我也有問過這題在12953 04/05 09:37
→ operationcow:不是0-1的背包問題,他每種東西都可以無限使用 04/05 09:45
推 netsphere:那我就不清楚了 XD 或許 Value/Weight值高先塞 04/05 09:50
推 Fenikso:你有沒有發現你的遞迴式沒用到p(n-1,*) XD 04/05 10:07
→ Fenikso:想想看要怎麼改進這點 04/05 10:08
→ operationcow:有, 應該怎麼使用呢?? 04/05 10:08
推 Fenikso:所以只要填p(n,0)~p(n,k)就好 複雜度馬上少個n XDD 04/05 10:12
→ Fenikso:加XDD好像很怪 不過上面說的是認真的(汗) 04/05 10:13
推 yoco315:XDDDDD 04/05 11:20
→ operationcow:了改:) 那nk已經是最低了嗎?? 04/05 14:48