→ bleed1979:請搜尋 "DJWS 背包" 空間是可以降, 時間就... 04/05 06:48
→ bleed1979:不然Backtracking..... 04/05 06:49
小弟我最近遇到了背包問題
題目敘述如下:
現有一背包可負載的重量為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
※ operationcow:轉錄至看板 C_and_CPP 04/05 04:02
※ 編輯: operationcow 來自: 220.131.228.139 (04/05 04:04)