Scribd
Upload
2 views2 pages

Knapsack Problem

The knapsack problem involves selecting items with given weights and profits to maximize total profit without exceeding a specified weight limit. There are two types of knapsack problems: the 0/1 knapsack problem, where items cannot be divided and must be taken whole, and the fractional knapsack problem, where items can be divided. The 0/1 knapsack problem is typically solved using dynamic programming, while the fractional knapsack problem is solved using a greedy approach.

Uploaded by

pharish0378280
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views2 pages

Knapsack Problem

The knapsack problem involves selecting items with given weights and profits to maximize total profit without exceeding a specified weight limit. There are two types of knapsack problems: the 0/1 knapsack problem, where items cannot be divided and must be taken whole, and the fractional knapsack problem, where items can be divided. The 0/1 knapsack problem is typically solved using dynamic programming, while the fractional knapsack problem is solved using a greedy approach.

Uploaded by

pharish0378280
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Knapsack problem

o Here knapsack is like a container or a bag.


o Suppose we have given some items which have some weights or profits.
o We have to put some items in the knapsack in such a way total value produces a
maximum profit.
o For example, the weight of the container is 20 kg.
o We have to select the items in such a way that the sum of the weight of items should be
either smaller than or equal to the weight of the container, and the profit should be
maximum.
There are two types of knapsack problems:
1. 0/1 knapsack problem
2. Fractional knapsack problem

0/1 knapsack problem


o The 0/1 knapsack problem means that the items are either completely or no items are
filled in a knapsack.
o For example, we have two items having weights 2kg and 3kg, respectively.
o If we pick the 2kg item then we cannot pick 1kg item from the 2kg item (item is not
divisible); we have to pick the 2kg item completely.
o This is a 0/1 knapsack problem in which either we pick the item completely or we will
pick that item.
o The 0/1 knapsack problem is solved by the dynamic programming.

Fractional knapsack problem


o The fractional knapsack problem means that we can divide the item.
o For example, we have an item of 3 kg then we can pick the item of 2 kg and leave the
item of 1 kg.
o The fractional knapsack problem is solved by the Greedy approach.

Example of 0/1 knapsack problem.


Consider the problem having weights and profits are:
Weights: {3, 4, 6, 5}
Profits: {2, 3, 1, 4}
The weight of the knapsack is 8 kg
The number of items is 4
The above problem can be solved by using the following method:

xi = {1, 0, 0, 1}

= {0, 0, 0, 1}

= {0, 1, 0, 1}
The above are the possible combinations.
o 1 denotes that the item is completely picked and 0 means that no item is picked.
o Since there are 4 items so possible combinations will be:
24 = 16;
o So. There are 16 possible combinations that can be made by using the above problem.
o Once all the combinations are made, we have to select the combination that provides the
maximum profit.
o Another approach to solve the problem is dynamic programming approach.
o In dynamic programming approach, the complicated problem is divided into sub-
problems, then we find the solution of a sub-problem and the solution of the sub-problem
will be used to find the solution of a complex problem.

You might also like