CODEWITHSUNDEEP
algorithmdynamic-programmingknapsack-problem
Ondrej
Ondrej

Reputation: 1017

Knapsack algorithm with special objects

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?

Upvotes: 1

Views: 539

Answers (1)

Codor
Codor

Reputation: 17605

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.

Upvotes: 5

Related Questions