小弟我最近遇到了背包问题 题目叙述如下: 现有一背包可负载的重量为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)