algorithm - 特殊元素背包算法

Question

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

所以，我们有 N 件元素，并且我们知道每件元素的重量/值(value)/特殊性。我们还定义了 S，它是特殊项目的最大数量。

有什么想法吗？

Answer 1

该问题可以建模为一个非几何背包问题，其中每个元素都有两个重量(即实际重量和第二个重量，当且仅当它特殊时 1 );第一个重量容量是背包容量，第二个重量容量是特殊元素所需的最大数量。根据this维基百科文章，该问题已知为 NP-complete 且不承认 FPTAS 除非 P=NP，但承认 FPTAS .显然，二维版本也承认类似于一维版本的动态规划算法。状态空间的语义如下，其中每个项目都有两个权重 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
              }

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