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

1. For each item or product, determine the profit-weight ratioratio.
2. Sort the elements in descending order according to ratioratio.
3. The product with the highest ratioratio should be taken and placed in a bag.
4. The amount the product weighs lessens the sack's capacity.
5. The product's profit margin increases the total profit.
6. 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.

Types of Knapsack Problem

The knapsack problem comes in various forms, each with its restrictions and objectives. Here are a few typical knapsack problems:

1. 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.
2. 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.
3. 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.
4. 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:

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:

 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:

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:

1. 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.
2. 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.
3. Iterative Dynamic Programming: Each item 'i' from 1 to 'num' and each capacity 'j' from 1 to ' maxw' are iterated using two arranged loops.
4. 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.
5. 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').
6.  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.
7. 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.
8. 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:

• 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.

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.

1. 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}}.
2. Iteration:
   1. Weight = 15 for i = 0, less than W. So include this item in your bag. Profit = 300, while the remainder W = 25 - 15 = 10.
   1. 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:

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

3.Unbounded Knapsack Problem: 

Maximizing without Repetition in the Unbounded Knapsack Problem.

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:

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.