CODEWITHSUNDEEP
algorithmdynamic-programmingknapsack-problem
Mariusz
Mariusz

Reputation: 1865

Knapsack algorithm variation

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?

Upvotes: 0

Views: 605

Answers (3)

Vikram Bhat
Vikram Bhat

Reputation: 6246

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.

Upvotes: 1

chill
chill

Reputation: 16888

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

Upvotes: 1

Sneftel
Sneftel

Reputation: 41464

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.

Upvotes: 2

Related Questions