C++ Program to Solve Knapsack Problem Using Dynamic Programming
The idea of knapsack dynamic programming is to store the solutions to solved subproblems in a table. You need only look at the table whenever you encounter a subproblem again. Consequently, algorithms created with dynamic programming are very efficient.
Problem Statement for the Knapsack Problem
The answer and the problem are explained using the Knapsack Problem. The term comes from the quantity of items that can only fit inside a pack of a set size. Considering the weight restriction, the objective is to fit as much value as you can into the knapsack out of a set of things with different weights and values.
The Dynamic Programming Solution for the 0-1 Knapsack Problem will now be analyzed.
Dynamic Programming-Based Solution to Solve the 0-1 Knapsack Problem
The actions listed below must be followed:
Weights and values for n items—six in this case—will first be given to us.
After that, to achieve the highest overall value in the knapsack, we will place these products in a knapsack with a capacity W of 12 kg.
The knapsack must be filled after placing the goods, but none can break. Hence, we have to choose whether to use the full object or not.
This can sometimes even result in a knapsack with some extra room.
Thus, this is how dynamic programming is used to solve the 0-1 knapsack.
Let's now use some basic C++ code to demonstrate this method in the application.
Applying the dynamic programming-based solution
To solve the 0-1 Knapsack Problem.
WWe have the weight of a collection of {9, 4, 2, 4, 5, 7} objects. Given a knapsack with a capacity of W=12, we must fill it.
Code:
#include <iostream>
#include <vector> // Include the vector header
using namespace std;
// Rename the max function to avoid conflicts with std::max
int maximum(int s, int k) {
if (s > k) // Corrected the comparison operator
return s;
else
return k;
}
int knapSack(int W, int wt[], int v[], int num) {
vector<vector<int>> K(num + 1, vector<int>(W + 1));
for (int i = 0; i <= num; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) // Corrected syntax error: added a closing parenthesis
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = maximum(v[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]); // Renamed max to maximum
else
K[i][w] = K[i - 1][w];
}
}
return K[num][W];
}
int main() {
int v[] = { 500, 250, 100, 60, 30, 10 };
int wt[] = { 9, 4, 2, 4, 5, 7 };
int W = 12;
int num = sizeof(v) / sizeof(v[0]);
cout << "Total amount stored in knapsack is " << knapSack(W, wt, v, num) << endl;
return 0;
}
Output:
![C++ Program to Solve Knapsack Problem Using Dynamic Programming/>
<!-- /wp:html -->
<!-- wp:heading {](https://static.tutorialandexample.com/cpp/cpp-program-to-solve-knapsack-problem-using-dynamic-programming1.png)
Implement the Dynamic Programming Solution to Solve the Fractional Knapsack Problem
The procedures listed below must be followed to solve the fractional Knapsack Problem:
We will be given the weights and values of n items—in this example, six items—much as in the 0-1 Knapsack Problem.
To obtain the maximum value of the knapsack, we will put these items in a knapsack with capacity W, or, in our example, 12 kg.
Next, we must fill the knapsack; however, in contrast to the 0-1 knapsack, we can break one item to obtain the knapsack's maximum value.
In this instance, we will divide the 4kg item into 2kg and 2kg parts to fill the knapsack.
Let's now apply this approach with simple C++ code.
Apply the Dynamic Programming-Based Approach to the Fractional Knapsack Problem Solving
We weight a collection of {9, 4, 2, 4, 5, 7} objects. Given a knapsack with a capacity of W=12, we must fill it, considering it a fractional knapsack.
Code:
#include <bits/stdc++.h>
using namespace std;
struct Obj {
int v, wt;
Obj(int v, int wt)
{
this->v=v;
this->wt=wt;
}
};
bool csort(struct Obj S, struct Obj K)
{
double D1 = (double)S.v / (double)S.wt;
double D2 = (double)K.v / (double)K.wt;
return D1 > D2;
}
double fracKnapsack(int W, struct Obj arr[], int Num)
{
sort(arr, arr + Num, csort);
/*
for (int i = 0; i < Num; i++)
{
cout << arr[i].v << " " << arr[i].wt << " :
"
<< ((double)arr[i].v / arr[i].wt) <<
endl;
}
*/
int cWt = 0;
double finalv = 0.0;
for (int i = 0; i < Num; i++) {
if (cWt + arr[i].wt <= W) {
cWt += arr[i].wt;
finalv += arr[i].v;
}
else {
int rem = W - cWt;
finalv += arr[i].v
* ((double)rem
/ (double)arr[i].wt);
break;
}
}
return finalv;
}
int main()
{
int W = 12;
Obj arr[] = { { 500, 9 }, { 250, 4 }, { 100, 2 }, { 60, 5 }, { 30, 5 }, { 10, 7 } };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum value we can get = "
<< fracKnapsack(W, arr, n);
return 0;
}
Output:
![C++ Program to Solve Knapsack Problem Using Dynamic Programming/>
<!-- /wp:html -->
<!-- wp:html -->
<div class=](https://static.tutorialandexample.com/cpp/cpp-program-to-solve-knapsack-problem-using-dynamic-programming2.png)