[問題] 請問背包問題寫成程式有沒有比較好的方法
※ [本文轉錄自 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)
推
04/05 09:19, , 1F
04/05 09:19, 1F
→
04/05 09:31, , 2F
04/05 09:31, 2F
推
04/05 09:37, , 3F
04/05 09:37, 3F
→
04/05 09:45, , 4F
04/05 09:45, 4F
推
04/05 09:50, , 5F
04/05 09:50, 5F
推
04/05 10:07, , 6F
04/05 10:07, 6F
→
04/05 10:08, , 7F
04/05 10:08, 7F
→
04/05 10:08, , 8F
04/05 10:08, 8F
推
04/05 10:12, , 9F
04/05 10:12, 9F
→
04/05 10:13, , 10F
04/05 10:13, 10F
推
04/05 11:20, , 11F
04/05 11:20, 11F
→
04/05 14:48, , 12F
04/05 14:48, 12F
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
