[問題] 請問背包問題寫成程式有沒有比較好的方法
看板Prob_Solve (計算數學 Problem Solving)作者operationcow (香蕉公車)時間15年前 (2009/04/05 04:00)推噓0(0推 0噓 2→)留言2則, 1人參與討論串1/1
小弟我最近遇到了背包問題
題目敘述如下:
現有一背包可負載的重量為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)
→
04/05 06:48, , 1F
04/05 06:48, 1F
→
04/05 06:49, , 2F
04/05 06:49, 2F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
