特殊物品背包算法

Question

我需要为扩展背包问题创建算法，其中我们有普通物品的特殊物品，我只能打包几个特殊物品。

所以，我们有 N 项，我们知道每一项的 weight/value/isSpecial。我们还定义了S，它是特殊物品的最大数量。

有什么想法吗？

Answer 1

问题可以建模为 non-geometric 背包问题，其中每个物品都有两个重量（即实际重量和第二个重量 1 当且仅当它是特别);第一个重量容量是背包容量，第二个重量容量是所需的最大数量 special 物品。根据this Wikipedia article, the problem is known to be NP-complete and does not admit an FPTAS unless P=NP, but admits an FPTAS。显然 two-dimensional 版本也承认类似于 one-dimensional 版本的动态规划算法。状态 space 的语义如下，其中每个项目都有两个权重 w1[i] 和 w2[i] 以及利润 p[i] 以及 C1 和 C2 是各自的容量。

P[i,j,k] := maximum profit attainable for items in {1,...,i} with weight
            in the first component at most j and weight in the second
            component at most k
            
            for any i in {1,...,N}
                    j in {1,...,C1}
                    k in {1,...,C2}

递推关系如下

P[i,j,k] = max{ P[i-1,j-w1[i],k-w2[k]] + p[i], // item i occurs
                P[i-1,j,k]                     // item i does not occur
              }

在实际实施中，需要进行一些索引检查以确定第一种情况是否真的会发生。

特殊物品背包算法

Knapsack algorithm with special objects

algorithm

knapsack-problem

dynamic-programming