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

Configuring Hadoop Cluster using Ansible !

What is this whole coding bootcamp thing?

Create better code using delegates and extension methods in Unity

Symfony 4: New Hope

Half-full or half-empty? A quick look at Optimistic vs. Pessimistic Rendering

How to configure Weight in BGP

AI Test Proctoring Has Social Bias and Students’ Grading Suffers

Spring Cloud Gateway

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

Traffic accidents have long been known as a systematic problem for every well-developed city…

Tuning Hyper Parameters of ML model on Top of AWS.

BIG Industries helps banks modernise in a customer-friendly way

The Linked List Data Structure