20/180: Knapsack Problems Data Structure

0–1 Knapsack:

//because if there are not items in the stack we cannot return //anything and if the limit is 0 in that can we cannot add any //weight inside the knapsack so ultimately resulting in 0.
if (n == 0 || w == 0){
return 0;
}
if(wt[n-1] <= W){
//If weight is less or equal we have choice weather to choose the
//them item or not. So for that we can find out the max from this
return max (val[n-1] + knapsack(wt, val, W-wt[n-1], n-1 ), knapsack(wt, val, W, n-1)) ;
}else
return knapsack(wt, val, W, n-1);
  1. Unbounded Knapsack: It is same like 0–1 Knapsack, except that we don’t have limit to choose the item, we can add the same item as many times we want. In 0–1 it was not like that, we have to decide only at the time of choosing the item if we need it or not, if yes then also we will go to the other item to pick, if not then also we will go to the next item to pick. But in unbounded knapsack we can pick the certain item as many time.
  2. Fractional Knapsack: Fractional Knapsack is a greedy approach, it doesn’t come in dynamic programming. In this we can divide one item into two depending on the capacity of knapsack. Let’s say Knapsack limit is 9 kg and we have one item of 18kg whose value is 100 and the other item is of 9kg whose value is 40, we can choose the one item with 18kg weight and divide it into have and will add only 9kg in knapsack ultimately having the maximum value i.e. is 50 which is greater than 40.

--

--

--

I am Indian by birth, Punjabi by destiny. Humanity is my religion. Love to eat, travel, read books and my million dreams keep me alive.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Podcast Episode 43 — Maintenance Matters

Turtle methods in python language

Salesforce API integration with Rails App.

Relevance Of Trying The DIY Platform And Its Importance To The Modern Age (Segment #5)

Event-Based Analytics (and BigQuery Export) comes to Google Analytics 4; How Does It Work … and…

Top 3 Reasons to Implement Reusable Components

Web Scrapping (HTML parsing and JSON API) using Python Spider-Scrapy

Understanding Docker Volumes with an example

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Navneet Ojha

Navneet Ojha

I am Indian by birth, Punjabi by destiny. Humanity is my religion. Love to eat, travel, read books and my million dreams keep me alive.

More from Medium

The Secret to Meaningful Technical Interviews

Two women sitting in an office having a technical interview

Cognizant Interview Experience

Designing a Tax-Efficient Salary Structure in India

My Journey as CP Lead at CodeChef GPREC Chapter