背包算法变异

Question

我有以下问题：

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

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

我必须找出背包能装的最大物品数是多少。

示例：

输入：

总计A：10，总计B：15

项目1 A:3，B:4

项目2 A： 7，B： 2

项目4 A:2，B:1

项目5 A:4，B:6

输出：

3（项目：2、3、4）

如何使用动态规划来解决此任务？

Answer 1

下面是一个可以帮助您的递归方程：-

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

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

Answer 2

定义m[i， wa， wb]为最大值（此处的项目计数），可以通过as的总和小于或等于wa和bs的总和小于或等于wb，使用高达i的项目。

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

如果<代码>项[i]. a

或

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

如果<代码>项[i]. a

Answer 3

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