Introduction to Knapsack Problem, its Types and How to solve them

The Knapsack problem is an example of the combinational optimization problem. This problem is also commonly known as the "Rucksack Problem". The name of the problem is defined from the maximization problem as mentioned below:

Given a bag with maximum weight capacity of W and a set of items, each having a weight and a value associated with it. Decide the number of each item to take in a collection such that the total weight is less than the capacity and the total value is maximized.

Knapsack Problem Description

Types of Knapsack Problem

The knapsack problem can be classified into the following types:

Fractional Knapsack Problem
0/1 Knapsack Problem
Bounded Knapsack Problem
Unbounded Knapsack Problem

Knapsack Steps

C# Implementation (Fractional Knapsack)

csharp

using System;
using System.Collections.Generic;

class GfG {

    // Comparison function to sort items based on value/weight ratio
    class ItemComparer : IComparer<int[]> {
        public int Compare(int[] a, int[] b) {
            double a1 = (1.0 * a[0]) / a[1];
            double b1 = (1.0 * b[0]) / b[1];
            return b1.CompareTo(a1);
        }
    }

    static double fractionalKnapsack(int[] val, int[] wt, int capacity) {
        int n = val.Length;

        // Create 2D array to store value and weight
        // items[i][0] = value, items[i][1] = weight
        int[][] items = new int[n][];
        for (int i = 0; i < n; i++) {
            items[i] = new int[2];
            items[i][0] = val[i];
            items[i][1] = wt[i];
        }

        // Sort items based on value-to-weight ratio in descending order
        Array.Sort(items, new ItemComparer());

        double res = 0.0;
        int currentCapacity = capacity;

        // Process items in sorted order
        for (int i = 0; i < n; i++) {
            // If we can take the entire item
            if (items[i][1] <= currentCapacity) {
                res += items[i][0];
                currentCapacity -= items[i][1];
            }
            // Otherwise take a fraction of the item
            else {
                res += (1.0 * items[i][0] / items[i][1]) * currentCapacity;
                // Knapsack is full
                break;
            }
        }

        return res;
    }

    static void Main() {
        int[] val = {60, 100, 120};
        int[] wt = {10, 20, 30};
        int capacity = 50;

        // Console.WriteLine(fractionalKnapsack(val, wt, capacity));
    }
}