作者operationcow (香蕉公车)
站内C_and_CPP
标题[问题] 请问背包问题写成程式有没有比较好的方法
时间Sun Apr 5 04:02:37 2009
※ [本文转录自 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)
1F：推 netsphere:填每一格需要O(n)好像有点高喔 04/05 09:19
2F：→ operationcow:那应该怎麽做呢??感谢感谢 04/05 09:31
3F：推 netsphere:要是我会从改进递回式开始 我也有问过这题在12953 04/05 09:37
4F：→ operationcow:不是0-1的背包问题,他每种东西都可以无限使用 04/05 09:45
5F：推 netsphere:那我就不清楚了 XD 或许 Value/Weight值高先塞 04/05 09:50
6F：推 Fenikso:你有没有发现你的递回式没用到p(n-1,*) XD 04/05 10:07
7F：→ Fenikso:想想看要怎麽改进这点 04/05 10:08
8F：→ operationcow:有, 应该怎麽使用呢?? 04/05 10:08
9F：推 Fenikso:所以只要填p(n,0)~p(n,k)就好 复杂度马上少个n XDD 04/05 10:12
10F：→ Fenikso:加XDD好像很怪 不过上面说的是认真的(汗) 04/05 10:13
11F：推 yoco315:XDDDDD 04/05 11:20
12F：→ operationcow:了改:) 那nk已经是最低了吗?? 04/05 14:48