CODEWITHSUNDEEP
dynamic-programmingknapsack-problem
IDERG
IDERG

Reputation: 5

Maximum and MinCost Knapsack

I am familiar with the 01 knapsack problem in that the goal is to put items in the knapsack that fit under the weight constraint. What is the difference between Maximum Knapsack and MinCost Knapsack? In which one am I given a budget or target value?

Upvotes: 0

Views: 1955

Answers (1)

rdj7
rdj7

Reputation: 1955

Explainig with examples

enter image description here

Here We have a Target/Budget value i.e. Weight, in this case m=20, Number of objects i.e. n=3,

weight of each object w1,w2,w3 and corresponding profits for these weights p1,p2,p3.

You can fill this sack in numerous ways but in the example they have shown profit values for 4 combinations of objects. Solution 4 gives max profit.

This is maximum knapsack because we have Profit values associated with each object and we need to fill this knapsack so that we maximize the profit.

Note: for 0-1 Knapsack values in above exapmle for x1,x2,x3 can't be fraction it has to be either 0 or 1.

NOTE: Also here object weights are the indices in array, starting at 1. i.e. w[] = {1,2,3,4,5}

cost[] is cost required when you add particular object.

If you add cost[1]=20 then w[1]=1 kg, cost[2]=10 then w[2]=2 kg and so on.

enter image description here

Here, also we have Target/Budget value i.e. Weight, in this case W=5, but we don't have profit values instead we have cost values. We need to minimize cost while filling this sack.

Upvotes: 1

Related Questions