带有特殊对象的背包算法

Question

我需要创建算法的扩展背包问题，其中我们有特殊的物品与正常的物品，我可以只打包几个特殊的物品。

所以，我们有N个项目，我们知道每个项目的权重/值/是特殊的。定义了特殊项的最大个数S。

你知道吗？

Answer 1

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
              }

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