Scribd
Upload
2 views7 pages

Knapsack Problem

The knapsack problem is an optimization challenge that seeks to maximize the value of items within a weight limit, with two main variations: 0/1 knapsack and fractional knapsack. The fractional knapsack allows for items to be divided, aiming to maximize profit with a time complexity of O(n logn). This problem has practical applications in resource allocation scenarios, such as project selection within budget constraints.

Uploaded by

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

Knapsack Problem

The knapsack problem is an optimization challenge that seeks to maximize the value of items within a weight limit, with two main variations: 0/1 knapsack and fractional knapsack. The fractional knapsack allows for items to be divided, aiming to maximize profit with a time complexity of O(n logn). This problem has practical applications in resource allocation scenarios, such as project selection within budget constraints.

Uploaded by

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

Knapsack Problem

Introduction
• The knapsack problem is a classic optimization problem that aims to maximize the
total value of items in a container (knapsack) without exceeding its weight
capacity.
• Given sets of items with specific weights and values, it requires selecting the
optimal combination.
• Generally two variations, 0/1 knapsack and fractional knapsack.
• The 0/1 variation requires items to be either entirely included or excluded, while
the fractional (continuous) variant allows taking fractions of items.
• Applications: frequently used for resource allocation, such as selecting projects
under a fixed budget, container loading etc.
Fractional Knapsack problem

• In this problem, items can be broken into smaller pieces, hence we can select
fractions of items.
• According to the problem statement,
• There are n items in the store
• Weight of ith item wi > 0
• Profit for ith item pi>0 and
• Capacity of the Knapsack is W
• The objective of the algorithm is to maximize the profit.
• Time complexity of the algorithm is O(n logn).
Example
• Consider the capacity of the knapsack W = 60 and the list of provided
items are shown in the following table:

Solution:

You might also like