小弟我最近遇到了背包問題 題目敘述如下: 現有一背包可負載的重量為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)