Johnnn

Let's go

0 – 1 knapsack problem and solution

by · Published · Updated

The 0/1 Knapsack problem is a classic optimization problem in computer science and mathematics. Given a set of items with their weights and values, and a knapsack with a maximum weight capacity, the goal is to determine the most valuable combination of items to include in the knapsack without exceeding its capacity. In this blog post, we will explore the algorithms to solve the 0/1 Knapsack problem and provide implementations in C, C++, Python, and Java. Let’s dive in!

Algorithm:
The problem can be solved using dynamic programming, specifically using a 2D table to store the intermediate results. The steps to solve the 0/1 Knapsack problem are as follows:

  1. Create a table of size (number of items + 1) x (knapsack capacity + 1).

  2. Initialize the first row and first column of the table with 0, as they represent the case of having no items or zero capacity.

  3. For each item, starting from the first item:

    • Iterate through each capacity from 1 to the knapsack capacity.
    • If the weight of the current item is less than or equal to the current capacity:
      • Calculate the maximum value between including and excluding the current item.
    • If the weight of the current item is greater than the current capacity:
      • Set the value in the table to the value obtained from excluding the current item.

  4. The final cell in the table will contain the maximum value achievable in the knapsack.

Implementations:

  1. C:
#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int knapsack(int capacity, int weights[], int values[], int n) {
    int table[n + 1][capacity + 1];

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= capacity; j++) {
            if (i == 0 || j == 0)
                table[i][j] = 0;
            else if (weights[i - 1] <= j)
                table[i][j] = max(values[i - 1] + table[i - 1][j - weights[i - 1]], table[i - 1][j]);
            else
                table[i][j] = table[i - 1][j];
        }
    }

    return table[n][capacity];
}

int main() {
    int values[] = {60, 100, 120};
    int weights[] = {10, 20, 30};
    int capacity = 50;
    int n = sizeof(values) / sizeof(values[0]);

    int maxValue = knapsack(capacity, weights, values, n);
    printf("The maximum value that can be achieved is: %dn", maxValue);

    return 0;
}
  1. C++:
#include <iostream>
#include <vector>
#include <algorithm>

int knapsack(int capacity, std::vector<int>& weights, std::vector<int>& values) {
    int n = weights.size();
    std::vector<std::vector<int>> table(n + 1, std::vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (weights[i - 1] <= j)
                table[i][j] = std::max(values[i - 1] + table[i - 1][j - weights[i - 1]], table[i - 1][j]);
            else
                table[i][j] = table[i - 1][j];
        }
    }

    return table[n][capacity];
}

int main() {
    std::vector<int> values = {60, 100, 120};
    std::vector<int> weights = {10, 20, 30};
    int capacity = 50;

    int maxValue = knapsack(capacity, weights, values);
    std::cout << "The maximum value that can be achieved is: " << maxValue << std::endl;

    return 0;
}
  1. Python:
def knapsack(capacity, weights, values):
    n = len(weights)
    table = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i - 1] <= j:
                table[i][j] = max(values[i - 1] + table[i - 1][j - weights[i - 1]], table[i - 1][j])
            else:
                table[i][j] = table[i - 1][j]

    return table[n][capacity]

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50

maxValue = knapsack(capacity, weights, values)
print("The maximum value that can be achieved is:", maxValue)
  1. Java:
public class Knapsack {
    public static int knapsack(int capacity, int[] weights, int[] values) {
        int n = weights.length;
        int[][] table = new int[n + 1][capacity + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (weights[i - 1] <= j)
                    table[i][j] = Math.max(values[i - 1] + table[i - 1][j - weights[i - 1]], table[i - 1][j]);
                else
                    table[i][j] = table[i - 1][j];
            }
        }

        return table[n][capacity];
    }

    public static void main(String[] args) {
        int[] values = {60, 100, 120};
        int[] weights = {10, 20, 30};
        int capacity = 50;

        int maxValue = knapsack(capacity, weights, values);
        System.out.println("The maximum value that can be achieved is: " + maxValue);
    }
}

Conclusion:
The 0/1 Knapsack problem is a widely studied optimization problem that can be efficiently solved using dynamic programming. By using a 2D table to store intermediate results, we can determine the most valuable combination of items to include in the knapsack without exceeding its capacity. Implementations in C, C++, Python, and Java have been provided to demonstrate the algorithm. By understanding and utilizing this problem-solving technique, you will be well-equipped to solve similar optimization problems efficiently.

You may also like...