有多个背包的01背包问题如何解决
  • 板块学术版
  • 楼主369Pai
  • 当前回复21
  • 已保存回复21
  • 发布时间2021/12/3 17:52
  • 上次更新2023/11/3 23:04:19
查看原帖
有多个背包的01背包问题如何解决
290023
369Pai楼主2021/12/3 17:52

题干

nn 个物品,每个物品都有价值 pp 与体积 vv

还有 mm 个背包,每个背包都有对应的容量 VV ,表示最多可以装的物品的体积之和不超过 VV

一个背包装过的东西另一个背包不能再装,两个背包不能合并。

求能获得的最大总价值。

疑问

如果是完全背包,应该是可以在 O(nm+m)O(nm+m) 的时间内解决的,即先跑一遍完全背包,再累加 f[Vi]f[V_i]

但能否给出这个问题的多项式时间复杂度解法?

2021/12/3 17:52
加载中...