完全背包与最短路

· · 个人记录

今天做一个最短路题，误认成背包，怎么也写不出来状态转移方程，结果突然想到用最短路，成功推出正解。

在思考的时候也有一个很神奇的思路冒出来了：

完全背包是不是可以用最短（长）路来做（限制条件众多但是这里仅提供一下思路）。

假设有一个体积为 V 的包，有 n 个体积为 v ，价值为 cnt 的物品。

1.建立 V+1 个点（编号 0 …… V ）。

2.建立一个数组 r 选择一个体积为 v 的物品所获得的最大价值

（

举个例子：

三个物品，一个体积为 3 ，价值为 4 ；一个体积为 3 ，价值为5；一个体积为 1 ，价值为 2 。

则 r[3]=5 ， r[1]=2 ->处理体积为负的情况时则需要对下标进行一定处理，如果没有对应体积的物品则将权值设定为 -inf ，则可以判断是否连边。

）

3.二重循环枚举每一个点对 (x,y) ，将 (x,y) 边权设为 r[y-x] （显然当 y<x 时将边权不连边即可 -> 处理体积为负的情况是则考虑这种情况下的连边即可）

然后 0 到 V 的单源最长路即可。

不难发现从源点到 V 选边的过程即为选择物品的过程。

时间复杂度：

  1. 对于体积均为正的物品来说，建立图为DAG，跑DAG最短路的时间复杂度 \Theta(V^2)

  2. 对于体积不一定为正的物品来说，建立图非DAG，跑Dijkstra最短路的时间复杂度 \Theta(V^2 \log V)

限制：时空复杂度偏高。

优势：可以处理有物品体积为负的完全背包问题（今天遇到的奇葩问题：选的过程中体积不能超过背包大小也不能为负）。

谢谢大家……

（

寻求大佬帮助：

  1. 该思想是否正确。

  2. 是否可以优化时空复杂度。

  3. 可否推广至其它类型背包问题。

）