Knapsack Problem in C++
A well-known optimization problem in math and computer science is the knapsack problem. Maximizing the total value while maintaining a predetermined weight limit entails choosing a subset of items from a given set, each with a specific weight and value. A good example of a combinational optimization issue is the Knapsack problem. The "Rucksack Problem" is another name for this problem.
The maximization problem serves as the basis for the problem's name, which is defined as follows:
Given a set of items, each with a weight and a value, and a bag with a maximum weight capacity of W. Choose how many of each item in a collection to bring so that the total weight is less than the allowed amount and the total worth is maximized.
Steps to Solve the Knapsack Problem
- For each item or product, determine the profit-weight ratioratio.
- Sort the elements in descending order according to ratioratio.
- The product with the highest ratioratio should be taken and placed in a bag.
- The amount the product weighs lessens the sack's capacity.
- The product's profit margin increases the total profit.
- Repeat the first three steps until the sack's capacity reaches 0 or until the sack is full.
Example:
Input:
N is equal to 3 things.
W = 3 (the bag's maximum weight capacity).
(Array of profits for each item) profit = 1, 2, 3.
weight [] = 4, 5, 6 (weights for each item in an array)
output: 0
Explanation:
The three options available to us in this situation, each with a matching profit and weight, are as follows. The objective is to maximize overall profit while limiting the total weight of the chosen items to what can fit in the bag.
However, due to the presented challenge's limitations, we cannot choose any objects that will fit inside the bag. Let's examine the components:
Item 1: Weight = 4 and Profit = 1.
Item 2: Weight = 5 and Profit = 2.
Item 3: Weight = 6 and Profit = 3.
All items in question may be chosen because they are within the bag's 3-item capacity. As a result, since we cannot select anything without going over the bag's weight limit, the highest profit that can be made in this situation is 0.
The output "0" denotes that no practical combination of goods can be chosen to fit into the specified capacity while producing a profit. The above is an instance where the constraints make it impossible to devise a solution that satisfies both the profit and weight requirements.
![Knapsack Problem in C++](https://static.tutorialandexample.com/cpp/knapsack-problem-in-cpp1.png)
Types of Knapsack Problem
The knapsack problem comes in various forms, each with its restrictions and objectives. Here are a few typical knapsack problems:
- 0/1 knapsack: The 0/1 Knapsack Problem is a version of the standard knapsack puzzle where each item can be taken 0 or 1 times. The objective is to maximize the overall value without exceeding the knapsack's capacity.
- Fractional Knapsack Problem: The fractional knapsack problem allows for non-integer amounts because items can be taken in fractions. Items can be separated to maximize the total value while staying within the capacity.
- Unbounded knapsack: The number of times an item may be selected is unlimited in this form of the knapsack puzzle. You can choose numerous examples to maximize the overall value while staying within the capacity constraints.
- Bounded knapsack: Unbounded and 0/1 knapsack problems are combined in the bounded knapsack problem. Each object has a maximum number of uses, often determined by the situation.
1. 0/1 knapsack Problem:
![Knapsack Problem in C++](https://static.tutorialandexample.com/cpp/knapsack-problem-in-cpp2.png)
Constraints:
- The rucksack can either have each item in it (0) or not (1), hence the name "0/1 Knapsack."
- Once something is in the knapsack, it cannot be separated or reduced to smaller pieces. Either everything is included, or nothing is included.
- The objective is to choose the best subset of items that maximize overall value while respecting the knapsack's capacity limitation.
Code:
#include <iostream>
#define MAX 10
using namespace std;
// Structure to store item information
struct sample
{
int num; // Item number
int gain; //Gain or Value of the item
int mass; //mass or weight of the item
float r; //Ratio of Gain to Mass for sorting
float quan; // Quantity of the item to take
};
int main()
{
sample arr[MAX], temp;
int i, j, totitems, knapcapacity;
float value = 0;
// Input the number of items and the knapsack capacity
cout << "Give the number of items: ";
cin >> totitems;
cout << "Give the max capacity of the bag: ";
cin >> knapcapacity;
cout << "\n";
// Input for items and calculation of their gain-to-mass ratios
for (i = 0; i < totitems; ++i)
{
arr[i].num = i + 1;
cout << "Enter the gain and mass for item " << i + 1 << " : ";
cin >> arr[i].gain >> arr[i].mass;
arr[i].r = (float)arr[i].gain / arr[i].mass;
arr[i].quan = 0;
}
// Sort items based on their gain-to-mass ratios in descending order
for (i = 0; i < totitems; ++i)
{
for (j = i + 1; j < totitems; ++j)
{
if (arr[i].r < arr[j].r)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
// Fill the knapsack using the greedy approach
for (i = 0; i < totitems; ++i)
{
if (knapcapacity == 0)
break;
else if (arr[i].mass <= knapcapacity)
{
arr[i].quan = 1;
knapcapacity -= arr[i].mass;
}
else if (arr[i].mass > knapcapacity)
{
arr[i].quan = (float)knapcapacity / arr[i].mass;
knapcapacity = 0;
}
}
// Display the selected items and the total value of the knapsack
cout << "The selected items from the bag:\n";
for (i = 0; i < totitems; ++i)
{
cout << "Take item " << arr[i].num << " : " << arr[i].quan * arr[i].mass << " units. ";
value += arr[i].gain * arr[i].quan;
}
cout << "\nThe max knapsack value is: " << value;
return 0;
}
Output:
![Knapsack Problem in C++](https://static.tutorialandexample.com/cpp/knapsack-problem-in-cpp3.png)
0/1 knapsack Problem by Using the Recursive Code:
The 0/1 Knapsack problem is solved using a recursive technique, which includes splitting the problem into smaller subproblems. Based on the capacity constraint, a decision is taken whether to include or exclude the current item at each step. Although conceptually simple, this method can be ineffective since it repeatedly calculates the same subproblems, increasing the problem's complexity exponentially over time.
Memorization is frequently employed to minimize this. By storing previously calculated results, this method prevents repeated calculations, thus increasing efficiency.
Despite its simplicity, the Recursive approach's time complexity makes it unworkable for bigger instances of the problem.
Code: For the recursive approach
#include <iostream>
using namespace std;
// Returns the maximum value that can be obtained
int recknapsack(int mass[], int price[], int knapcapacity, int number) {
// Base case: No items left or knapsack is full
if (number == 0 || knapcapacity == 0) // Changed 'capacity' to 'knapcapacity'
return 0;
// If the current item's weight exceeds the knapsack capacity, skip it
if (mass[number - 1] > knapcapacity) // Changed 'n' to 'number'
return recknapsack(mass, price, knapcapacity, number - 1);
// Return the maximum of two cases:
// 1. Including the current item
// 2. Excluding the current item
return max(price[number - 1] + recknapsack(mass, price, knapcapacity - mass[number - 1], number - 1),
recknapsack(mass, price, knapcapacity, number - 1));
}
int main() {
int mass[] = {56, 23, 9, 7};
int price[] = {660, 12, 19, 86};
int knapcapacity = 16;
int number = sizeof(price) / sizeof(price[0]); // Changed 'values' to 'price'
int maxprofit = recknapsack(mass, price, knapcapacity, number);
cout << "The Maximum profit value is : " << maxprofit << endl;
return 0;
}
Output:
![Knapsack Problem in C++](https://static.tutorialandexample.com/cpp/knapsack-problem-in-cpp4.png)
More effective techniques like dynamic programming provide superior solutions by reducing the duplication included by the recursive approach.
Knapsack using Dynamic Programming
This C++ program solves the 0-1 knapsack problem using dynamic programming. In this case, a group of items is given, each with a weight and an associated value. The goal is to determine the ideal number of each item in the collection. The above should be done while maximizing the overall cumulative value so that the cumulative weight stays below or equal to the defined limit.
The fundamental concept represents each cell in a table (often a 2D array) as a subproblem. The columns show the capacity from 0 to the maximum permitted weight, while the rows correspond to the items considered. This table can be filled out iteratively so that we can eventually arrive at the best possible outcome.
The general framework of the dynamic programming strategy for the knapsack problem is as follows:
- Create a Table DP[n+1][W+1]: A two-dimensional table DP is established in this phase and used to record intermediate outcomes. The table size is (num + 1) rows and (maxw + 1) columns, where num is the total number of items and maxw is the knapsack's maximum weight limitation.
- Initialize Base Cases: The DP table's first row and column are initialized to zeros. The creation of the dynamic programming solution depends on this stage. The first column represents a knapsack with no weight capacity, and the first row corresponds to the condition of having no items.
- Iterative Dynamic Programming: Each item 'i' from 1 to 'num' and each capacity 'j' from 1 to ' maxw' are iterated using two arranged loops.
- For each of the DP table's cells (i, j): If the weight of the existing item 'i' is less than or equal to the capacity 'j', it determines whether keeping the existing item would be more beneficial.
- The value at cell (i, j) is set to the maximum value from the cell above, representing not including the current item: DP[i - 1][j] if the item's weight can be accommodated ('mass[i - 1] <= j').
- DP[i - 1][j - mass[i - 1]] + price[i - 1] represents includes the current item by adding the value from the cell (i - 1, j - mass[i - 1]) and the value of the current item.
- Final Outcome: Following the dynamic programming iteration, the best outcome is saved in the DP table's cell (num, maxw). The output should be the highest value that may be obtained while e considering all goods and the maximum weight allowed.
- Backtrack for Selected Items (Optional): Although backtracking isn't explicitly included in this code snippet, you can do so by traversing the DP table. You may trace the route leading to the ideal value and determine which things were chosen to attain it by looking at how the DP table was filled.
Code:
The code effectively solves the problem using a bottom-up dynamic programming strategy.
#include <iostream>
#include <vector>
using namespace std;
int knapsack(int s, vector<int>& mass, vector<int>& price) {
int num = mass.size();
vector<vector<int>> DP(num + 1, vector<int>(s + 1, 0));
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= s; j++) {
if (mass[i - 1] <= j) { // Changed s to j
DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - mass[i - 1]] + price[i - 1]); // Changed s to j
} else {
DP[i][j] = DP[i - 1][j]; // Changed w to j
}
}
}
return DP[num][s];
}
int main() {
int maxw; // Maximum weight capacity
cout << "Enter the max capacity of the bag: ";
cin >> maxw;
int num; // Number of items
cout << "Enter the number of items: ";
cin >> num;
vector<int> mass(num); // Item weights
vector<int> price(num); // Item values // Changed n to num
cout << "Enter the weights of items: ";
for (int i = 0; i < num; ++i) { // Changed n to num
cin >> mass[i];
}
cout << "Enter the values of items: ";
for (int i = 0; i < num; ++i) { // Changed n to num
cin >> price[i];
}
int maxValue = knapsack(maxw, mass, price); // Changed W to maxw, weight to Mass, Value to price
cout << "Maximum value: " << maxValue << endl;
return 0;
}
Output:
![Knapsack Problem in C++](https://static.tutorialandexample.com/cpp/knapsack-problem-in-cpp5.png)
- Time Complexity: O (num * s), where num is the number of items and s is the knapsack capacity.
- Space Complexity: O (num * s), where num is the number of items and s is the knapsack capacity.
2. Fractional Knapsack Problem:
Another form of the knapsack problem is the fractional knapsack problem, although, in this instance, you can choose fractions of the objects rather than only entire ones. So long as you don't exceed the weight limit of the knapsack, you can take a portion of an item that maximizes the overall worth. A greedy algorithm is typically used to solve this problem.
![Knapsack Problem in C++](https://static.tutorialandexample.com/cpp/knapsack-problem-in-cpp6.png)
Example:
arr[] = {{150, 5}, {200, 8}, {100, 2}}, W = 10
The knapsack's capacity has already exceeded when the complete item weighing 5 kg plus the entire item weighing 2 kg is considered (5 + 2 = 7 kg). There are 3 kilograms of capacity left. We can now take a portion of the 8 kg object that still fits in the available space:
An item weighing 8 kg divided by 3 equals 0.375(3/8).
Total Value: Value of item weighing 5 kg + value of item weighing 2 kg + fraction of value of item weighing 8 kg.
Total value = 250 (150 + 100 + 0.375 * 200).
Therefore, 250 is the total value that may be obtained while still fitting inside the knapsack's 10 kg weight limit.
Using the Greedy Algorithm, we will be solving the Fractional Knapsack Problem.
The Fractional Knapsack greedy strategy involves the following:
- Calculating each item's profit-to-weight ratioratio.
- Arranging the items in descending order according to this ratioratio.
- Repeat going through the sorted objects and putting as much of them, fully or partially, into the knapsack.
This strategy guarantees the largest profit accumulation by giving the items with the best profit-to-weight ratioratio the highest priority at each stage.
Let us understand the above with the below example:
Take the following example: arr[] = {{250, 10}, {300, 15}, {200, 8}}, W = 25.
- Sorting: The array should be arranged according to the profit/weight ratio. The sorted array will have the values {{300, 15}, {250, 10}, {200,8}}.
- Iteration:
- Weight = 15 for i = 0, less than W. So include this item in your bag. Profit = 300, while the remainder W = 25 - 15 = 10.
- Weight = 10 for i = 1, which is less than W. Add this item as well. Profit = 300+250 =550, and the remaining W =10-10=0.
- There are no more items, and the knapsack is full. Thus, the final profit for W = 25 is 550.
Code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Struct to represent an item sample
struct Sample {
int price; // Price (Value) of the item
int mass; //mass (weight) of the item
double ratioratio; //ratioratio of price to mass
};
// Function to compare two items based on ratioratio in descending order
bool compare(Sample a, Sample b) {
return a.ratio > b.ratio;
}
// Fractional Knapsack algorithm implementation
double fractionalKnapsack(int capacity, vector<Sample>& samples) {
double result = 0.0;
int currentCapacity = capacity;
// Sort samples based on ratio in descending order
sort(samples.begin(), samples.end(), compare);
// Iterate through sorted samples and add items to knapsack
for (int i = 0; i < samples.size(); ++i) {
if (samples[i].mass <= currentCapacity) {
// Add the full item's price to the
result += samples[i].price;
// Update current capacity by subtracting the item's mass
currentCapacity -= samples[i].mass;
} else {
// Add a fraction of the item's price based on the remaining capacity
result += (samples[i].ratio * currentCapacity);
break; // Knapsack is full
}
}
return result;
}
int main() {
int n; // Number of items
cout << "Enter the number of items: ";
cin >> n;
vector<Sample> samples(n);
cout << "Enter the price and mass of items:" << endl;
for (int i = 0; i < n; ++i) {
cin >> samples[i].price >> samples[i].mass;
// Calculate the price-to-mass ratio for each item
samples[i].ratio = (double)samples[i].price / samples[i].mass;
}
int capacity;
cout << "Enter the max capacity of the knapsack: ";
cin >> capacity;
// Calculate maximum profit using fractional knapsack algorithm
double maxProfit = fractionalKnapsack(capacity, samples);
cout << "The Maximum profit by using fractional knapsack is: " << maxProfit << endl;
return 0;
}
Output:
![Knapsack Problem in C++](https://static.tutorialandexample.com/cpp/knapsack-problem-in-cpp7.png)
The provided C++ program for the Fractional Knapsack problem sorts items according to their price-to-mass ratioratio and iterates through them to fill the knapsack while maximizing profit. As a result, the sorting process takes up.
The time complexity of O(n log n),
space complexity of O(n) in the program.
Differences between 0/1 and Fractional Knapsack
Aspect | 0/1 knapsack | Fractional knapsack |
Problem Statement | Select items with values and weights to maximize total value while staying within a knapsack's weight capacity. | Same as 0/1 Knapsack but can take fractions of items. |
Item Selection | Items can only be taken in full (1) or not taken at all (0). | Items can be taken in fractions between 0 and 1. |
Solution Space | Discrete: Limited possible solutions due to binary inclusion/exclusion. | Continuous: More flexible solution space due to fractional selection. |
Algorithms | Typically solved using dynamic programming techniques. | Often solved using greedy algorithms. |
Optimal Solution | Generally, requires more complex algorithms for optimal solutions due to discrete choices. | The greedy algorithm can find an optimal solution, sorting items based on value-to-weight ratioratio. |
Time Complexity | Dynamic programming approach has a higher time complexity. | The greedy approach has a lower time complexity. |
Example | Given items: (value, weight) - [(3, 2), (4, 3), (5, 4), (8, 5)], Knapsack capacity = 5. Solution: Select items: [(0, 1), (1, 0), (1, 0), (0, 1)], Total value = 9. | Given items: (value, weight) - [(3, 2), (4, 3), (5, 4), (8, 5)], Knapsack capacity = 5. Solution: Take fractions of item 1 and item 3 to fill the knapsack. Total value ≈ 7.75. |
3.Unbounded Knapsack Problem:
Maximizing without Repetition in the Unbounded Knapsack Problem.
![Knapsack Problem in C++](https://static.tutorialandexample.com/cpp/knapsack-problem-in-cpp8.png)
The standard knapsack problem can be modified to allow for an unlimited number of each item by using the Unbounded Knapsack problem. The Unbounded Knapsack Problem allows for repeating items in the knapsack, unlike the 0/1 Knapsack Problem, where each item can only be selected once. With this improvement, the solution space is more adaptable and dynamic, making it particularly relevant to situations where objects can be purchased in any number of amounts.
Problem statement:
Given a set of items, each with a value and a weight, and a knapsack with a finite capacity, what should I choose to maximize the total value while staying within the weight limit? Unlike the conventional knapsack variations, there are no limitations on how often an item can be selected.
Main logic:
// Dynamic programming table initialization
dp[i] = 0
// Dynamic programming recurrence relation
dp[i] = max(dp[i], dp[i-weights[j]] + values[j]
where j varies from 0
to n-1 such that:
weights[j] <= i)
// Final result using the dynamic programming table
result = dp[capacity]
By using dynamic programming, implementing the above logic:
#include <iostream>
#include <vector>
using namespace std;
int unbounded_knapsack(vector<int>& values, vector<int>& weights, int capacity) {
int n = values.size();
vector<int> dp(capacity + 1, 0);
for (int i = 1; i <= capacity; ++i) {
for (int j = 0; j < n; ++j) {
if (weights[j] <= i) {
dp[i] = max(dp[i], dp[i - weights[j]] + values[j]);
}
}
}
return dp[capacity];
}
int main() {
vector<int> values = {10, 30, 20};
vector<int> weights = {5, 10, 15};
int capacity = 100;
int max_value = unbounded_knapsack(values, weights, capacity);
cout << "Maximum value: " << max_value << endl;
return 0;
}
Output:
![Knapsack Problem in C++](https://static.tutorialandexample.com/cpp/knapsack-problem-in-cpp9.png)
4. Bounded knapsack:
In the Bounded Rucksack Problem, things must be chosen to maximize total value while remaining within the weight limit of a rucksack. Items in this version have a limited supply, unlike the Unbounded version. The objective is to find the ideal blend while keeping weight and quantity restrictions in mind. Dynamic programming addresses it and can be used in resource allocation and inventory management situations.
Advantages of the Knapsack Problem
- Resource Allocation in Finance: By choosing a combination of assets or projects to maximize returns while staying within a budget, the knapsack problem can be utilized to optimize investment decisions.
- Rucksack packing in travel planning: When choosing products for a trip, keep in mind that you must stay within the weight restrictions of your rucksack.
- Cutting Stock Problem: The cutting stock problem is a variation of the knapsack problem employed in producing paper, textiles, and metal. Meeting orders while reducing waste requires figuring out the most effective approach to cutting huge rolls of material into smaller pieces.
- Employee Scheduling: The knapsack problem can be used in employee scheduling and workforce management to choose the optimal tasks or shifts for employees while considering their availability and skill sets.
- Drug Discovery: Based on their prospective efficacy and production costs, compounds can be optimally chosen for synthesis using the knapsack problem in drug discovery.
- Portfolio management: Creating well-balanced portfolios is essential in the financial industry. The knapsack problem makes choosing investments that will yield the highest returns while staying within a given budget easier.