背包算法的变化

Question

我遇到了以下问题：

有一组项目，每个项目都有2个不同的正值a和B。

背包有两个值：totalA和totalB。其是所选项目的值A和值B的最大和。

我必须弄清楚，背包能装的最大物品数是多少。

示例：

输入：

总计A:10，总计B:15

项目1 A:3，B:4

项目2 A:7，B:2

项目3 A:1，B:9

项目4 A:2，B:1

项目5 A:4，B:6

输出：

3（项目：2、3、4）

我应该如何使用动态编程来解决此任务？

Answer 1

这被称为"多重约束背包问题"（MKP，偶尔被渲染为d-KP）。它可以像正则背包问题一样在伪多项式时间内求解，但你需要一个二维表而不是一个。

Answer 2

将m[i，wa，wb]定义为最大值（此处为项目数），可在as之和小于或等于wa，bs之和小于等于wb的情况下获得，使用最多为i的项目。

m[i,wa,wb] = m[i-1,wa,wb]

如果item[i].a > wa或item[i].b > wb

或

m[i,wa,wb] =  max (m[i-1, wb, wb], m[i-1, wa - item[i].a, wb - item[i].b] + 1)

如果item[i].a <= wa和item[i].b <= wb

Answer 3

这里有一个递归方程可能会对您有所帮助：-

if(Items[N].b<=Wa && Items[N].b<=Wa)
    Value(N,Wa,Wb) = max(1+Value(N-1,Wa-Items[N].a,Wb-Items[N].b),Value(N-1,Wa,Wb)) 
else Value(N,Wa,Wb) = Value(N-1,Wa,Wb)
Where Wa = Current capacity of A sack & Wb of B sack
      N = no of items considered

注意：您可以在递归解决方案上使用哈希表实现，这将防止三维数组。