knapsack problem

-

 

What is a knapsack problem? 

    Suppose you have given a knapsack or bag with a limited weight capacity, and each item has some weight and value. The problem here is that "Which item is to be placed in the knapsack such that the weight limit does not exceed and the total value of the items is as large as possible?".

Consider the real-life example. Suppose there is a thief and he enters the museum. The thief contains the knapsack, or we can say bag that has limited weight capacity. The museum contains various items of different values. The thief decides what items are should he keep in the bag so that profit would become maximum.

Some important points related to the knapsack problem are:

  • It is a combinatorial optimization-related problem.
  • Given a set of N items - usually numbered from 1 to N; each of these items has a mass wi and a value vi.
  • It determines the number of each item to be included in a collection so that the total weight M is less than or equal to a given limit and the total value is as large as possible.
  • The problem often arises in resource allocation where there are financial constraints.

 

Suppose we have a knapsack of 15 kg, so M = 15 kg. It means that the total weight of the knapsack is 15 kg. The total weight of the items to be included in the knapsack should have the weight less than or equal to the M. Some items are given which have some key features, i.e., weight of the item, and the value of the item. As we can observe below that the first item has the weight as 12kg and the value as $4, second item has the weight as 2kg and the value as $2, third item has the weight as 1 kg and the value as $1, fourth item has the weight as 4 kg and the value as $10, and the fifth item has the weight as 1 kg and the value as the $2. Here, we have to decide whether we have to include the item or not.

Knapsack problem variants

There are two variants of knapsack problem:

  • 0/1 knapsack problem: In the case of 0/1 knapsack problem, items are indivisible. Here, indivisible means that we cannot break an item. In this, we can either take an item or not. We either take the item completely and keep in the knapsack or we leave the item completely. There is no possibility that we keep some fraction of the item in the knapsack.

Here, '0' means that we are not taking that item and '1' means that we are taking the item completely. This type of problem is solved by using the dynamic programming approach.

Some important points related to the 0/1 Knapsack problem are:

  • In this problem, we cannot take the fraction of the items. Here, we have to decide whether we have to take the item, i.e., x = 1 or not, i.e., x = 0.
  • The greedy approach does not provide the optimal result in this problem.
  • Another approach is to sort the items by cost per unit weight and starts from the highest until the knapsack is full. Still, it is not a good solution. Suppose there are N items. We have two options either we select or exclude the item. The brute force approach has O(2N) exponential running time. Instead of using brute force approach, we use the dynamic programming approach to obtain the optimal solution.

1.      Dynamic-0-1-knapsack (v, w, n, W)   

2.      for w = 0 to W do   

3.       c[0, w] = 0   

4.      for i = 1 to n do   

5.         c[i, 0] = 0   

6.         for w = 1 to W do   

7.            if wi ? w then   

8.               if vi + c[i-1, w-wi] then   

9.                  c[i, w] = vi + c[i-1, w-wi]   

10.             else c[i, w] = c[i-1, w]   

11.                 else   

12.          c[i, w] = c[i-1, w]

  M.Sarulatha
Assistant Professor 
  

M.


Comments

Post a Comment

Popular posts from this blog

Operating System Structure

-
Image
M.Sarulatha Monolithic System  or Simple System: A monolithic system structure refers to a software architecture where all components are tightly integrated into a single, self-contained unit. This means that the entire system is built as a single executable file, with all functionality and data stored within it. Characteristics of Monolithic Systems: 1. Tight Coupling: Components are heavily interconnected and interdependent. 2. Single Executable: The entire system is built into a single executable file. 3. Centralized Data: Data is stored within the single executable or in a centralized database. 4. No External Dependencies: The system does not rely on external services or components. Advantages of Monolithic Systems: 1. Simple to Develop: Easier to build and test, as everything is self-contained. 2. Fast Deployment: Quicker to deploy, as only a single executable needs to be deployed. 3. Easy Maintenance: Simpler to maintain, as all components are within a single codebase. Disa...
Read more

Asymptotic Notations

-
Image
Asymptotic Notations: Asymptotic Notations are mathematical tools used to analyze the performance of algorithms by understanding how their efficiency changes as the input size grows. These notations provide a concise way to express the behavior of an algorithm’s time or space complexity as the input size approaches infinity. Rather than comparing algorithms directly, asymptotic analysis focuses on understanding the relative growth rates of algorithms’ complexities. It enables comparisons of algorithms’ efficiency by abstracting away machine-specific constants and implementation details, focusing instead on fundamental trends. Asymptotic analysis allows for the comparison of algorithms’ space and time complexities by examining their performance characteristics as the input size varies. By using asymptotic notations, such as Big O, Big Omega, and Big Theta, we can categorize algorithms based on their worst-case, best-case, or average-case time or space complexities, providing valuable in...
Read more

ASP.NET Events Handling

-
Image
  ASP.NET  Events Handling M.SARULATHA Assistant Professor Dept. of CA,JJC.           ASP.NET provides important feature event handling to Web Forms. It let us to implement event-based model for our application. As a simple example, we can add a button to an ASP.NET Web Forms page and then write an event handler for the button's click event. ASP.NET Web Forms allows events on both client and server sides.           In ASP.NET Web Forms pages, however, events associated with server controls originate on the client but are handled on the Web server by the ASP.NET.           ASP.NET Web Forms follow a standard .NET Framework pattern for event-handler methods. All events pass two arguments: an object representing the object that raised the event, and an event object containing any event-specific information. Example: Creating Event Hand...
Read more