有 nnn 个物品,每个物品都有价值 ppp 与体积 vvv 。
还有 mmm 个背包,每个背包都有对应的容量 VVV ,表示最多可以装的物品的体积之和不超过 VVV 。
一个背包装过的东西另一个背包不能再装,两个背包不能合并。
求能获得的最大总价值。
如果是完全背包,应该是可以在 O(nm+m)O(nm+m)O(nm+m) 的时间内解决的,即先跑一遍完全背包,再累加 f[Vi]f[V_i]f[Vi] 。
但能否给出这个问题的多项式时间复杂度解法?