Knapsack algorithm variation

0
votes

I've got a following problem:

There is a set of items, every item has 2 different positive values A and B.

The knapsack has two values: totalA and totalB. which are the maximum sums of values A and B of chosen items.

I have to find out, what the maximum items count the knapsack can hold is.

Example:

Input:

totalA: 10, totalB: 15

item1 A:3, B: 4

item2 A:7, B: 2

item3 A:1, B: 9

item4 A:2, B: 1

item5 A:4, B: 6

Output:

3(items: 2, 3, 4)

How should I use dynamic programming in order to solve this task?

3
algorithmdynamic-programmingknapsack-problem
possible duplicate stackoverflow.com/questions/14103846/… or stackoverflow.com/questions/14137267/… - mamdouh alramadan
The posts you linked to contain answers to a classic knapsack problem, where every item has its weight and value. Items in my case dont have values, but they have two weights. - Mariusz

3 Answers

2
votes

This is known as the "multiply-constrained knapsack problem" (MKP, occasionally rendered as d-KP). It can be solved in pseudopolynomial time just like the regular knapsack problem, but you need a two-dimensional table instead of one.

1
votes

Define m[i,wa,wb] to be the maximum value (count of items here), that can be attained with sum of as being less than or equal to wa and sum of bs being less than or equal to wb, using items up to i.

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

if item[i].a > wa or item[i].b > wb

or

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

if item[i].a <= wa and item[i].b <= wb

1
votes

Here is an recurrence equation that might help you :-

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

Note: You can use a hash table implementation on recursive solution which would prevent of three dimensional array.