Difference Between Greedy Knapsack and 0/1 Knapsack Algorithms

Difference between 0/1 Knapsack problem and Fractional Knapsack problem

The 0/1 Knapsack algorithm is a dynamic programming approach where items are either completely included or not at all. It considers all combinations to find the maximum total value. On the other hand, the Greedy Knapsack algorithm, also known as the Fractional Knapsack, allows for items to be broken into fractions, selecting items with the highest value-to-weight ratio first. However, this approach may not provide the optimal solution for the 0/1 Knapsack problem.

Greedy Knapsack Algorithm:

The greedy knapsack is an algorithm for making decisions that have to make a locally optimal choice at each stage in the hope that this will eventually lead to the best overall decision. In other words, it chooses items that have high value-to-weight ratios by iteratively selecting them based on increasing cost-benefit ratio whereby those items whose price can be paid less per unit utility derived from them are always preferred over others. Therefore, at any point in time, it just picks the item with a higher value/weight ratio without considering future consequences.

Steps of the Greedy Knapsack Algorithm:

Find out value-to-weight ratios for all items: This implies dividing the worth of every item by its weight.
Rearrange items according to their value-to-weight ratios: Order them according to who has first got the highest ratio.
Go through the sorted list: Starting from the highest rationed item add items to the knapsack until there’s no more leftover space or no more other considerations about components.

Example:

Suppose we have a knapsack with a capacity of 50 units and the following items with their respective values and weights:

Item 1: Value = 60, Weight = 10
Item 2: Value = 100, Weight = 20
Item 3: Value = 120, Weight = 30

Using the greedy approach, we sort the items based on their value-to-weight ratio:

Item 3 (120/30 = 4)
Item 2 (100/20 = 5)
Item 1 (60/10 = 6)

Now, starting with the highest ratio, we add items to the knapsack until its capacity is reached:

Knapsack: Item 3 (Value: 120, Weight: 30) + Item 2 (Value: 100, Weight: 20)
Total Value: 220

Implementation:

C++

#include <bits/stdc++.h>
using namespace std;

// Structure for an item which stores weight and
// corresponding value of Item
struct Item {
    int value, weight;

    // Constructor
    Item(int value, int weight)
        : value(value)
        , weight(weight)
    {
    }
};

// Comparison function to sort Item according to
// value/weight ratio
bool cmp(struct Item a, struct Item b)
{
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 > r2;
}

// Main greedy function to solve problem
double fractionalKnapsack(int W, struct Item arr[], int n)
{
    //    sorting Item on basis of ratio
    sort(arr, arr + n, cmp);

    //    Uncomment to see new order of Items with their
    //    ratio
    /*
    for (int i = 0; i < n; i++) {
        cout << arr[i].value << "  " << arr[i].weight << " :
    " << ((double)arr[i].value / arr[i].weight) << endl;
    }
    */

    int curWeight = 0; // Current weight in knapsack
    double finalvalue = 0.0; // Result (value in Knapsack)

    // Looping through all Items
    for (int i = 0; i < n; i++) {
        // If adding Item won't overflow, add it completely
        if (curWeight + arr[i].weight <= W) {
            curWeight += arr[i].weight;
            finalvalue += arr[i].value;
        }

        // If we can't add current Item, add fractional part
        // of it
        else {
            int remain = W - curWeight;
            finalvalue
                += arr[i].value
                   * ((double)remain / arr[i].weight);
            break;
        }
    }

    // Returning final value
    return finalvalue;
}

// Driver code
int main()
{
    int W = 50; //    Weight of knapsack
    Item arr[] = { { 60, 10 }, { 100, 20 }, { 120, 30 } };

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Maximum value we can obtain = "
         << fractionalKnapsack(W, arr, n);
    return 0;
}

Java

import java.util.Arrays;
import java.util.Comparator;

// Structure for an item which stores weight and
// corresponding value of Item
class Item {
    int value, weight;

    // Constructor
    public Item(int value, int weight)
    {
        this.value = value;
        this.weight = weight;
    }
}

public class Main {
    // Comparison function to sort Item according to
    // value/weight ratio
    static class ItemComparator
        implements Comparator<Item> {
        public int compare(Item a, Item b)
        {
            double r1 = (double)a.value / a.weight;
            double r2 = (double)b.value / b.weight;
            if (r1 < r2)
                return 1;
            else if (r1 > r2)
                return -1;
            return 0;
        }
    }

    // Main greedy function to solve problem
    static double fractionalKnapsack(int W, Item arr[],
                                     int n)
    {
        // sorting Item on basis of ratio
        Arrays.sort(arr, new ItemComparator());

        int curWeight = 0; // Current weight in knapsack
        double finalValue
            = 0.0; // Result (value in Knapsack)

        // Looping through all Items
        for (int i = 0; i < n; i++) {
            // If adding Item won't overflow, add it
            // completely
            if (curWeight + arr[i].weight <= W) {
                curWeight += arr[i].weight;
                finalValue += arr[i].value;
            }
            else {
                // If we can't add current Item, add
                // fractional part of it
                int remain = W - curWeight;
                finalValue
                    += arr[i].value
                       * ((double)remain / arr[i].weight);
                break;
            }
        }

        // Returning final value
        return finalValue;
    }

    // Driver code
    public static void main(String[] args)
    {
        int W = 50; // Weight of knapsack
        Item arr[] = { new Item(60, 10), new Item(100, 20),
                       new Item(120, 30) };
        int n = arr.length;

        System.out.println("Maximum value we can obtain = "
                           + fractionalKnapsack(W, arr, n));
    }
}

Python

from typing import List

# Class representing an item with value and weight


class Item:
    def __init__(self, value: int, weight: int):
        self.value = value
        self.weight = weight

# Function to compare items based on value/weight ratio


def item_comparator(a: Item, b: Item) -> int:
    r1 = a.value / a.weight
    r2 = b.value / b.weight
    if r1 < r2:
        return 1
    elif r1 > r2:
        return -1
    return 0

# Main greedy function to solve the problem


def fractional_knapsack(W: int, arr: List[Item]) -> float:
    # Sorting items based on ratio
    arr.sort(key=lambda x: item_comparator(x, x))

    cur_weight = 0  # Current weight in knapsack
    final_value = 0.0  # Result (value in Knapsack)

    # Looping through all items
    for item in arr:
        # If adding the item won't overflow, add it completely
        if cur_weight + item.weight <= W:
            cur_weight += item.weight
            final_value += item.value
        else:
            # If we can't add the current item, add fractional part of it
            remain = W - cur_weight
            final_value += item.value * (remain / item.weight)
            break

    # Returning the final value
    return final_value


# Driver code
if __name__ == "__main__":
    W = 50  # Weight of knapsack
    arr = [Item(60, 10), Item(100, 20), Item(120, 30)]
    print("Maximum value we can obtain =", fractional_knapsack(W, arr))

JavaScript

// Structure for an item which stores weight and
// corresponding value of Item
class Item {
    constructor(value, weight) {
        this.value = value;
        this.weight = weight;
    }
}

// Comparison function to sort Item according to
// value/weight ratio
function cmp(a, b) {
    let r1 = a.value / a.weight;
    let r2 = b.value / b.weight;
    return r1 > r2;
}

// Main greedy function to solve problem
function fractionalKnapsack(W, arr) {
    // sorting Item on basis of ratio
    arr.sort(cmp);

    let curWeight = 0; // Current weight in knapsack
    let finalvalue = 0.0; // Result (value in Knapsack)

    // Looping through all Items
    for (let i = 0; i < arr.length; i++) {
        // If adding Item won't overflow, add it completely
        if (curWeight + arr[i].weight <= W) {
            curWeight += arr[i].weight;
            finalvalue += arr[i].value;
        }

        // If we can't add current Item, add fractional part of it
        else {
            let remain = W - curWeight;
            finalvalue += arr[i].value * (remain / arr[i].weight);
            break;
        }
    }

    // Returning final value
    return finalvalue;
}

// Driver code
let W = 50; // Weight of knapsack
let arr = [new Item(60, 10), new Item(100, 20), new Item(120, 30)];

console.log("Maximum value we can obtain = ", fractionalKnapsack(W, arr));

Output

Maximum value we can obtain = 240

0/1 Knapsack Algorithm:

An alternative approach of the dynamic programming is taken by the 0/1 Knapsack Algorithm unlike that which is greedy. This is why it was named “0/1” since it completely takes or leaves each item which is a binary decision. The algorithm guarantees an overall optimal but can become very expensive for large number of problem sizes.

Steps of the 0/1 Knapsack Algorithm:

Create a table: A table will be initialized to store maximum value that can be obtained with different weights and items.
Fill the table iteratively: For every item and every possible weight, determine whether including the item would increase its value without exceeding the weight limit.
Use the table to determine the optimal solution: Follow through backward in order to find items that have been included in optimal solution.

Example:

Suppose we have a knapsack with a capacity of 5 units and the following items with their respective values and weights:

Item 1: Value = 6, Weight = 1
Item 2: Value = 10, Weight = 2
Item 3: Value = 12, Weight = 3

We construct a dynamic programming table to find the optimal solution:

0/1 Knapsack

Finally, we find that the optimal solution is to include Item 2 and Item 3:

Knapsack: Item 2 (Value: 10, Weight: 2) + Item 3 (Value: 12, Weight: 3)
Total Value: 22