Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide To Understand The Differences Between Stack And Queue

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 11

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 12

The Definitive Guide to Understand Stack vs Heap Memory Allocation

Lesson - 13

All You Need to Know About Linear Search Algorithm

Lesson - 14

All You Need to Know About Breadth-First Search Algorithm

Lesson - 15

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 16

The Best Tutorial to Understand Trees in Data Structure

Lesson - 17

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 18

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 19

All You Need to Know About Tree Traversal in Data Structure

Lesson - 20

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 21

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 22

The Best and Easiest Way to Understand an Algorithm

Lesson - 23

Your One-Stop Solution to Understand Shell Sort Algorithm

Lesson - 24

Your One-Stop Solution to Quick Sort Algorithm

Lesson - 25

The Most Useful Guide to Learn Selection Sort Algorithm

Lesson - 26

Everything You Need to Know About Radix Sort Algorithm

Lesson - 27

Everything You Need to Know About the Counting Sort Algorithm

Lesson - 28

Everything You Need to Know About the Merge Sort Algorithm

Lesson - 29

Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

Lesson - 30

Everything You Need to Know About the Bubble Sort Algorithm

Lesson - 31

The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

Lesson - 32

Your One-Stop Solution to Understand Recursive Algorithm in Programming

Lesson - 33

The Definitive Guide to Understanding Greedy Algorithm

Lesson - 34

Your One-Stop Solution to Understand Backtracking Algorithm

Lesson - 35

The Fundamentals of the Bellman-Ford Algorithm

Lesson - 36

Your One-Stop Solution for Graphs in Data Structures

Lesson - 37

The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

Lesson - 38

A Simplified and Complete Guide to Learn Space and Time Complexity

Lesson - 39

All You Need to Know About the Knapsack Problem : Your Complete Guide

Lesson - 40

The Fibonacci Series: Mathematical and Programming Interpretation

Lesson - 41

The Holistic Look at Longest Common Subsequence Problem

Lesson - 42

The Best Article to Understand What Is Dynamic Programming

Lesson - 43

A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

Lesson - 44

A Holistic Guide to Learn Stop Solution Using Dynamic Programming

Lesson - 45

One Stop Solution to All the Dynamic Programming Problems

Lesson - 46

Understanding the Fundamentals of Binomial Distribution

Lesson - 47
All You Need to Know About the Knapsack Problem : Your Complete Guide

Knapsack dynamic programming works on the principle of using a table to store the answers to solved subproblems. If you come into a subproblem again, all you have to do is look up the answer in the table. As a result, dynamic programming-designed algorithms are incredibly efficient.

By the end of this article, you will be able to understand how to solve the problem of 0-1 and fractional knapsack using dynamic programming with the necessary details and practical implementations.

Problem Statement for the Knapsack Problem

Knapsack_Problem-statement-img1

The Knapsack Problem is used to explain both the problem and the solution. It derives its name from the limited number of things that may be carried in a fixed-size knapsack. We are given a set of items with varying weights and values; the goal is to store as much value as possible into the knapsack while staying within the weight limit.

Now, let us look at the Dynamic Programming Based Solution to Solve the problem of 0-1 Knapsack.

Post Graduate Program: Full Stack Web Development

in Collaboration with Caltech CTMEEnroll Now
Post Graduate Program: Full Stack Web Development

Dynamic Programming Based Solution to Solve the 0-1 Knapsack Problem

Knapsack_Problem-0-1-solution-img1.

We must follow the below given steps:

  1. First, we will be provided weights and values of n items, in this case, six items.
  2. We will then put these items in a knapsack of capacity W or, in our case, 10kg to get the maximum total value in the knapsack.
  3. After putting the items, we have to fill this knapsack, but we can't break the item. So, we must either pick the entire item or skip it.
  4. Sometimes this may even lead to a knapsack with some spare space left with it.

So, this is how we solve the 0-1 knapsack using dynamic programming. Now let's implement this solution through a simple C++ code.

Implement the Dynamic Programming Based Solution to Solve the 0-1 Knapsack Problem

We are given the weight of a collection of items {6, 3, 3, 2, 2, 2} and a knapsack of capacity W=10. We have to fill this knapsack, considering it as 0-1 knapsack.

Code:

// A c++ program to solve 0-1 Knapsack problem using dynamic programming

#include <bits/stdc++.h>

using namespace std;

// A function to returns a maximum of two numbers

int max(int X, int Y)

{

if(X>Y)

return X;

else

return Y;

}

// A function to returns the maximum value

// that can be stored in a knapsack of W=10

int knapSack(int W, int wt[], int val[], int n)

{

int i, w;

vector<vector<int>> K(n + 1, vector<int>(W + 1));

// Build table K[][] in bottom up manner

for(i = 0; i <= n; i++)

{

for(w = 0; w <= W; w++)

{

if (i == 0 || w == 0)

K[i][w] = 0;

else if (wt[i - 1] <= w)

K[i][w] = max(val[i - 1] +K[i - 1][w - wt[i - 1]], K[i - 1][w]);

else

K[i][w] = K[i - 1][w];

}

}

return K[n][W];

}

int main()

{

int val[] = { 300, 150, 120, 100, 90, 80 };

int wt[] = { 6, 3, 3, 2, 2, 2 };

int W = 10;

int n = sizeof(val) / sizeof(val[0]);

cout << knapSack(W, wt, val, n);

return 0;

}

Knapsack_Problem-0-1-implementation-img1

This method has a time complexity of O(N*W). 

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

Dynamic Programming Based Solution to Solve the Fractional Knapsack Problem

Knapsack_Problem-fractional-solution-img1

We have to follow the below given steps to solve the fractional Knapsack Problem:

  1. Similar to the 0-1 Knapsack Problem, we will be given weights and values of n items, in this case, six items.
  2. We will put these items in a knapsack of capacity W or, in our case, 10kg to get the total maximum value in the knapsack.
  3. Then, we have to fill this knapsack, but unlike 0-1 knapsack, we can even break an item to get the maximum value of the knapsack.  
  4. In this case, to fill the knapsack, we will break the 3kg item into 2kg and 1kg items.

Now let's implement this solution through a simple C++ code.

Implement the Dynamic Programming Based Solution to Solve the Fractional Knapsack Problem

We will be provided with the weight of a collection of items {6, 3, 3, 2, 2, 2}. We are given a knapsack of capacity W=10 and we have to fill this knapsack, considering it as a fractional knapsack.

Code: 

//A C++ program to illustrate a 

//fractional Knapsack Problem solution using dynamic programming 

#include <bits/stdc++.h>

using namespace std;

// A structure to define Item

struct Item {

int val, wt;

// Constructor

Item(int val, int wt)

{

this->val=val;

this->wt=wt;

}

};

//A function to sort Item according to Val/wt ratio

bool cmpsort(struct Item X, struct Item Y)

{

double R1 = (double)X.val / (double)X.wt;

double R2 = (double)Y.val / (double)Y.wt;

return R1 > R2;

}

// Main greedy function to solve the problem

double fractionalKnapsack(int W, struct Item arr[], int N)

{

// sorting Item on basis of ratio

sort(arr, arr + N, cmpsort);

// Uncomment to see new order of Items with their

// ratio

/*

for (int i = 0; i < N; i++)

{

cout << arr[i].val << " " << arr[i].wt << " :

"

<< ((double)arr[i].val / arr[i].wt) <<

endl;

}

*/

int curWt = 0; // Current weight in knapsack

double finalval = 0.0; 

// Iterating through all Items

for (int i = 0; i < N; i++) {

// If adding Item won't overflow, add it completely

if (curWt + arr[i].wt <= W) {

curWt += arr[i].wt;

finalval += arr[i].val;

}

// If we can't add the current Item, add fractional of it

else {

int rem = W - curWt;

finalval += arr[i].val

* ((double)rem

/ (double)arr[i].wt);

break;

}

}

// Returning final value

return finalval;

}

int main()

{

int W = 10; // Weight of knapsack

Item arr[] = { { 300, 6 }, { 150, 3 }, { 120, 3 }, { 100, 2 }, { 90, 2 }, { 80, 2 } };

int n = sizeof(arr) / sizeof(arr[0]);

cout << "Maximum value we can obtain = "

<< fractionalKnapsack(W, arr, n);

return 0;

}

Knapsack_Problem-fractional-implementation-img1

With this, we have come to an end of this article. We will now look at what could be your next steps to conquer dynamic programming problems.

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Next Steps

Your next stop in mastering dynamic programming problems should be the Longest Common Substring Problem. The Longest Common Substring Problem involves determining the longest string which is a substring of two or more strings. There are several solutions to the problem.

If you're searching for a more in-depth understanding of software development that can help you carve out a successful career in the field, look no further. Take up Simplilearn's Postgraduate Program in Full Stack Web Development, which is offered in collaboration with Caltech CTME, the world's largest technology education institution. This Post Graduate Program will teach you how to grasp both front-end and back-end Java technologies; we will begin with the basics and move to more sophisticated Full Stack Web Development subjects. In this web development course, you'll study Angular, Spring Boot, Hibernate, JSPs, and MVC, which will help you get started as a full-stack developer. 

If you have any questions or require clarification on this "Knapsack Problem" article, please leave them in the comments section below. Our expert team will review them and respond as soon as possible.

About the Author

Vaibhav KhandelwalVaibhav Khandelwal

Vaibhav Khandelwal is a proactive tech geek who's always on the edge of learning new technologies. He is well versed in competitive programming and possess sound knowledge of web development. He likes to read fictional and sci-fi novels and likes to play strategy games like chess.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.