Knapsack algorithm with special objects

Question

I need to create algorithm for extended Knapsack problem, where we have special items with normal items and I can pack only several special items.

So, we have N items and we know weight/value/isSpecial of each one. Also we have defined S, which is maximum number of special items.

Any idea?

Please formalize it, and then check out if integer-programming is a viable approach. — sascha
– sascha, Commented Mar 29, 2018 at 11:36
Can you not treat the special items restriction identically to the weight restriction? — myrtlecat
– myrtlecat, Commented Mar 29, 2018 at 11:52
@myrtlecat No, you can not. You just have simple list of items with weights/values and knowledge about each item whether is special or not. You can work with special items just as with common, but each time you use special-one, you have to increase counter which can not exceed given number (usually small one) — Ondrej
– Ondrej, Commented Mar 30, 2018 at 12:41
If I understand correctly, the restriction on special items can be reformulated as a second weight restriction as follows: common items have a "special weight" of 0, special items have a "special weight" of 1, and the total "special weight" must not exceed S. Mathematically, the original weight restriction and the "special weight" restriction can be treated identically, and that gives @Codor's solution below. — myrtlecat
– myrtlecat, Commented Mar 30, 2018 at 13:00

Community · Accepted Answer · 2020-06-20 09:12:55Z

5

The problem can be modeled as a non-geometric knapsack problem where each item has two weights (namely the actual weight and a second weight which is 1 if and only if it is special); the first weight capacity is the knapsack capacity and the second weight capacity is the desired maximum number of special items. According to this Wikipedia article, the problem is known to be NP-complete and does not admit an FPTAS unless P=NP, but admits an FPTAS. Apparently the two-dimensional version also admits a dynamic programming algorithm similar to the one-dimensional version. The semantics of the state space would be as follows, where each item has two weights w1[i] and w2[i] and profit p[i] and where C1 and C2 are the respective capacities.

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}

The recurrence relation would be as follows.

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
              }

In an actual implementation, some index checking would be necessary to determine whether the first case can actuallty occur.

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Mar 29, 2018 at 11:52

Codor

17.6k9 gold badges32 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ondrej Over a year ago

nice answer, thank you. Could you provide code or more detailed pseudocode as well?

Collectives™ on Stack Overflow

Knapsack algorithm with special objects

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related