Knapsack Problem: 0-1 and Fractional Using Dynamic Programming

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

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.

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

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

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;

}

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

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

Dynamic Programming Based Solution to Solve the Fractional Knapsack Problem

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;

}

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.