Practical session

Duration2h30

Presentation & objectives

Important

The aim of this session is to help you master important notions in computer science. An intelligent programming assistant such as GitHub Copilot, that you may have installed already, will be able to provide you with a solution to these exercises based only on a wisely chosen file name.

For the sake of training, we advise you to disable such tools first.

At the end of the practical activity, we suggest you to work on the exercise again with these tools activated. Following these two steps will improve your skills both fundamentally and practically.

Also, we provide you the solutions to the exercises. Make sure to check them only after you have a solution to the exercises, for comparison purpose! Even if you are sure your solution is correct, please have a look at them, as they sometimes provide additional elements you may have missed.

Activity contents

1 — The O-1 knapsack problem

The problem is the following (quoted from Comer et al.).

A thief robbing a store wants to take the most valuable load that can be carried in a knapsack capable of carrying at most $W$ pounds of loot. The thief can choose to take any subset of $n$ items in the store. The $i$th item is worth $v_i$ dollars and weighs $w_i$ pounds, where $v_i$ and $w_i$ are integers. Which items should the thief take?

Remark: The problem is called the 0-1 knapsack problem because the thief can either take an item or leave it, but cannot take a fraction of an item.

For this exercise, we will create a file knapsack.py and implement various solutions to the 0-1 knapsack problem. In parallel, we will create a file test_knapsack.py to test the functions implemented in knapsack.py. We will not only check the correctness of the functions but also their efficiency.

As a base parameter, we will consider the following values:

The maximum weight the knapsack can carry: $W = 50$.
The list of weights of the items: $weights = [10, 20, 30]$.
The list of values of the items: $values = [60, 100, 120]$.

Two additional sets of parameters will be considered for the tests:

$W = 15$, $weights = [12, 7, 11, 8, 9]$, $values = [24, 13, 23, 15, 16]$.
$W = 30$, $weights = [2, 3, 5, 7, 1, 4, 6, 8, 10, 9, 2, 3, 5, 7, 1]$, $values = [10, 15, 7, 8, 4, 12, 6, 11, 20, 18, 5, 9, 14, 16, 3]$.

The fist set of parameters is small enough to allow you to compute the results by hand. The two other sets of parameters are larger and will require the implementation of efficient algorithms and feel the complexity of each approach.

1.1 — Solution by hand

Forget about the program, take a pen and some paper and consider the first test example. List all the possible combinations of items that can be taken, and for each of them, compute the total weight and the total value. Then, determine the combination that maximizes the total value without exceeding the maximum weight the knapsack can carry. This solution will help you understand the problem and the expected results.

1.2 —A recursive solution

The first function to implement is a recursive solution to the 0-1 knapsack problem. The function should have the following signature:

def knapsack_recursive(W: int, weights: List[int], values: List[int]) -> int:
    """ Recursive solution to the 0-1 knapsack problem.
        In: 
            - W: the maximum weight the knapsack can carry
            - weights: the list of weights of the items
            - values: the list of values of the items
        Out:
            - the maximum value that can be carried in the knapsack
    """
    pass

The recursive solution is simply based on the optimal-substructure property of the problem: if the most valuable load includes item $i$, then the remaining load must be the most valuable load weighing at most $W - w_i$ that the thief can take from the original items, excluding item $i$.

Hints

Click here to reveal the hints.

Use a recursive helper function that includes an additional paramater $n$ indicating the current item to check. The base case of the recursivity is that their is no more items to study or not more space in the knapsack. The recursive calls correspond to the case where the current item is to heavy to be added to the knapsack and to the cases where the item is taken or not. The best solution of these two last possibilities has to be returned.

Correction

Click here to reveal the answer.

def knapsack_recursive(W: int, weights: list[int], values: list[int]) -> int:
    """ Recursive solution to the 0-1 knapsack problem.
        In: 
            - W: the maximum weight the knapsack can carry
            - weights: the list of weights of the items
            - values: the list of values of the items
        Out:
            - the maximum value that can be carried in the knapsack
    """

    def knapsack_recursive_helper(W: int, weights: list[int], values: list[int], n: int) -> int:
        """ Helper function to solve the 0-1 knapsack problem recursively.
            In:
                - W: the maximum weight the knapsack can carry
                - weights: the list of weights of the items
                - values: the list of values of the items
                - n: the current item to pick or not (corresponds to weights[n-1] and values[n-1])
            Out:
                - the maximum value that can be carried in the knapsack
        """
        # base case no items to check or no more space left
        if n == 0 or W == 0:
            return 0
        # if the current item is too heavy, skip it
        if weights[n - 1] > W:
            return knapsack_recursive_helper(W, weights, values, n - 1)
        else:
            # return the maximum of two cases:
            # 1. the current item is included
            # 2. the current item is not included
            return max(values[n - 1] + knapsack_recursive_helper(W - weights[n - 1], weights, values, n - 1),
                       knapsack_recursive_helper(W, weights, values, n - 1))
        
    return knapsack_recursive_helper(W, weights, values, len(weights))

#test case 1
W = 15
weights = [12, 7, 11, 8, 9]
values = [24, 13, 23, 15, 16]
print(knapsack_recursive(W, weights, values)) # 28
#test case 2
W = 30
weights = [2, 3, 5, 7, 1, 4, 6, 8, 10, 9, 2, 3, 5, 7, 1]
values = [10, 15, 7, 8, 4, 12, 6, 11, 20, 18, 5, 9, 14, 16, 3]
print(knapsack_recursive(W, weights, values)) # 90

public class Knapsack {

    public static int knapsackRecursive(int W, int[] weights, int[] values) {
        return knapsackRecursiveHelper(W, weights, values, weights.length);
    }

    private static int knapsackRecursiveHelper(int W, int[] weights, int[] values, int n) {
        // base case no items to check or no more space left
        if (n == 0 || W == 0) {
            return 0;
        }
        // if the current item is too heavy, skip it
        if (weights[n - 1] > W) {
            return knapsackRecursiveHelper(W, weights, values, n - 1);
        } else {
            // return the maximum of two cases:
            // 1. the current item is included
            // 2. the current item is not included
            return Math.max(values[n - 1] + knapsackRecursiveHelper(W - weights[n - 1], weights, values, n - 1),
                            knapsackRecursiveHelper(W, weights, values, n - 1));
        }
    }

    public static void main(String[] args) {
        // test case 1
        int W1 = 15;
        int[] weights1 = {12, 7, 11, 8, 9};
        int[] values1 = {24, 13, 23, 15, 16};
        System.out.println(knapsackRecursive(W1, weights1, values1)); // 28

        // test case 2
        int W2 = 30;
        int[] weights2 = {2, 3, 5, 7, 1, 4, 6, 8, 10, 9, 2, 3, 5, 7, 1};
        int[] values2 = {10, 15, 7, 8, 4, 12, 6, 11, 20, 18, 5, 9, 14, 16, 3};
        System.out.println(knapsackRecursive(W2, weights2, values2)); // 90
    }
}

1.3 — A recursive solution with memoization

A second step is to implement a recursive solution with memoization. The function should have the following signature:

def knapsack_recursive_memo(W: int, weights: List[int], values: List[int]) -> int:
    """ Recursive solution with memoization to the 0-1 knapsack problem.
        In: 
            - W: the maximum weight the knapsack can carry
            - weights: the list of weights of the items
            - values: the list of values of the items
        Out:
            - the maximum value that can be carried in the knapsack
    """
    pass

The recursive solution with memoization consists of storing the results of the subproblems in a table to avoid recomputing them.

Correction

Click here to reveal the answer.

def knapsack_recursive_memo(W: int, weights: list[int], values: list[int]) -> int:
    """ Recursive solution with memoization to the 0-1 knapsack problem.
        In: 
            - W: the maximum weight the knapsack can carry
            - weights: the list of weights of the items
            - values: the list of values of the items
        Out:
            - the maximum value that can be carried in the knapsack
    """
    # Create a table to store the results of the subproblems
    table = [[-1 for _ in range(W + 1)] for _ in range(len(values) + 1)]
    
    def knapsack_recursive_with_memo(W: int, weights: list[int], values: list[int], n: int) -> int:
        """ Helper function to solve the 0-1 knapsack problem recursively with memoization.
            In: 
                - W: the maximum weight the knapsack can carry
                - weights: the list of weights of the items
                - values: the list of values of the items
                - n: the number of items
            Out:
                - the maximum value that can be carried in the knapsack
        """
        # If the result is not already computed
        if table[n][W] == -1:
            # Base case: no item to take or no space left in the knapsack
            if n == 0 or W == 0:
                table[n][W] = 0
            # If the weight of the nth item is more than the knapsack capacity, then this item cannot be included in the optimal solution
            elif weights[n - 1] > W:
                table[n][W] = knapsack_recursive_with_memo(W, weights, values, n - 1)
            else:
                # Return the maximum of two cases:
                table[n][W] = max(values[n - 1] + knapsack_recursive_with_memo(W - weights[n - 1], weights, values, n - 1),
                                    knapsack_recursive_with_memo(W, weights, values, n - 1))        
        # Return the result
        return table[n][W]
    
    return knapsack_recursive_with_memo(W, weights, values, len(weights))
# Test the function
assert knapsack_recursive_memo(50, [10, 20, 30], [60, 100, 120]) == 220

public class Knapsack {

    public static int knapsackRecursiveMemo(int W, int[] weights, int[] values) {
        int n = values.length;
        int[][] table = new int[n + 1][W + 1];
        
        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                table[i][w] = -1;
            }
        }

        return knapsackRecursiveWithMemo(W, weights, values, n, table);
    }

    private static int knapsackRecursiveWithMemo(int W, int[] weights, int[] values, int n, int[][] table) {
        if (table[n][W] == -1) {
            if (n == 0 || W == 0) {
                table[n][W] = 0;
            } else if (weights[n - 1] > W) {
                table[n][W] = knapsackRecursiveWithMemo(W, weights, values, n - 1, table);
            } else {
                table[n][W] = Math.max(values[n - 1] + knapsackRecursiveWithMemo(W - weights[n - 1], weights, values, n - 1, table),
                                       knapsackRecursiveWithMemo(W, weights, values, n - 1, table));
            }
        }
        return table[n][W];
    }

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

        // Test case 1
        W = 15;
        weights = new int[]{12, 7, 11, 8, 9};
        values = new int[]{24, 13, 23, 15, 16};
        long start = System.nanoTime();
        System.out.println(knapsackRecursiveMemo(W, weights, values)); // 28
        System.out.printf("Time taken with memo: %.6f seconds%n", (System.nanoTime() - start) / 1e9);

        // Test case 2
        W = 30;
        weights = new int[]{2, 3, 5, 7, 1, 4, 6, 8, 10, 9, 2, 3, 5, 7, 1};
        values = new int[]{10, 15, 7, 8, 4, 12, 6, 11, 20, 18, 5, 9, 14, 16, 3};
        start = System.nanoTime();
        System.out.println(knapsackRecursiveMemo(W, weights, values)); // 28
        System.out.printf("Time taken with memo: %.6f seconds%n", (System.nanoTime() - start) / 1e9);
    }
}

1.4 — A dynamic programming solution

A third step is to implement a dynamic programming solution to the 0-1 knapsack problem. The function should have the following signature:

def knapsack_dp(W: int, weights: List[int], values: List[int], n: int) -> int:
    """ Dynamic programming solution to the 0-1 knapsack problem.
        In: 
            - W: the maximum weight the knapsack can carry
            - weights: the list of weights of the items
            - values: the list of values of the items
            - n: the number of items
        Out:
            - the maximum value that can be carried in the knapsack
    """
    pass

Unlike the memoization solution, the dynamic programming solution fills the table in a bottom-up manner.

Hints

Click here to reveal the hints.

To implement the dynamic programming solution, follow these steps:

Initialize the table: Create a matrix with dimensions (n+1) x (W+1) where n is the number of items and W is the maximum weight the knapsack can carry. Initialize all values to 0.
Fill the table: Iterate through each item and each weight capacity, filling the table based on the following conditions:
- If the current item’s weight is greater than the current capacity, the value is the same as the value without including the current item.
- Otherwise, the value is the maximum of either including the current item or not including it.
Return the result: The value at table[n][W] will be the maximum value that can be carried in the knapsack.

Correction

Click here to reveal the answer.

def knapsack_dp(W: int, weights: list[int], values: list[int], n: int) -> int:
    """ Dynamic programming solution to the 0-1 knapsack problem.
        In: 
            - W: the maximum weight the knapsack can carry
            - weights: the list of weights of the items
            - values: the list of values of the items
            - n: the number of items
        Out:
            - the maximum value that can be carried in the knapsack
    """
    # Create a matrix to store the results of the subproblems
    table = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
    # for each item in the list
    # the first row is for the case of no item, so we start at 1
    for i in range(1, n+1): 
        # for each weight in the knapsack
        for j in range(1, W+1):
            # if the weight of the item is greater than the current weight
            # note that i starts at 1, so the weight of the item is weights[i-1] 
            if weights[i - 1] > j:
                # the value is the same as the value without including the current item
                table[i][j] = table[i - 1][j]
            else:
                # the value is the maximum of either including the current item or not including it
                table[i][j] = max(table[i - 1][j], values[i - 1] + table[i - 1][j - weights[i - 1]])
    return table[n][W]
    
# Test the function
assert knapsack_dp(50, [10, 20, 30], [60, 100, 120], 5) == 220

import java.util.Arrays;

public class KnapsackDP {

    public static int knapsackDP(int W, int[] weights, int[] values, int n) {
        // Create a table to store the results of the subproblems
        int[][] table = new int[n+1][W + 1];
        // for each item in the list
        // the first row is for the case of no item, so we start at 1
        for (int i = 0; i <= values.length; i++) {
            // for each weight in the knapsack from W to the (weight in cell i) - 1
            for (int j = 0; j <= weights.length; w++) {
                // if the weight of the item is greater than the current weight
                // note that i starts at 1, so the weight of the item is weights[i-1]
                if(weights[i - 1] > j){
                    // the value is the same as the value without including the current item
                    table[i][j] = table[i - 1][j]
                }else{
                    // the value is the maximum of either including the current item or not including it
                    table[i][j] = max(table[i - 1][j], values[i - 1] + table[i - 1][j - weights[i - 1]])
                } 
            }
        }
        return table[n][W];
    }

    public static void main(String[] args) {
        // Test the function
        assert knapsackDP(50, new int[]{10, 20, 30}, new int[]{60, 100, 120}, 5) == 220;

        // test case 1
        int W = 15;
        int[] weights = {12, 7, 11, 8, 9};
        int[] values = {24, 13, 23, 15, 16};
        long start = System.nanoTime();
        System.out.println(knapsackDP(W, weights, values, 5)); // 28
        long elapsed = System.nanoTime() - start;
        System.out.printf("Time taken without memo: %.6f seconds%n", elapsed / 1e9);

        W = 30;
        weights = new int[]{2, 3, 5, 7, 1, 4, 6, 8, 10, 9, 2, 3, 5, 7, 1};
        values = new int[]{10, 15, 7, 8, 4, 12, 6, 11, 20, 18, 5, 9, 14, 16, 3};
        start = System.nanoTime();
        System.out.println(knapsackDP(W, weights, values, 15)); // 28
        elapsed = System.nanoTime() - start;
        System.out.printf("Time taken with memo: %.6f seconds%n", elapsed / 1e9);
    }
}

1.5 — A greedy solution

The last step is to implement a greedy solution to the 0-1 knapsack problem. The function should have the following signature:

def knapsack_greedy(W: int, weights: List[int], values: List[int]) -> int:
    """ Greedy solution to the 0-1 knapsack problem.
        In: 
            - W: the maximum weight the knapsack can carry
            - weights: the list of weights of the items
            - values: the list of values of the items
        Out:
            - the maximum value that can be carried in the knapsack
    """
    pass

The greedy solution consists of selecting the item with the maximum value-to-weight ratio until the knapsack is full.

Correction

Click here to reveal the answer.

def knapsack_greedy(W: int, weights: List[int], values: List[int], n: int) -> int:
    """ Greedy solution to the 0-1 knapsack problem.
        In: 
            - W: the maximum weight the knapsack can carry
            - weights: the list of weights of the items
            - values: the list of values of the items
            - n: the number of items
        Out:
            - the maximum value that can be carried in the knapsack
    """
    # Create a list of tuples (value, weight, value-to-weight ratio)
    items = [(values[i], weights[i], values[i] / weights[i]) for i in range(n)]
    # Sort the items by value-to-weight ratio in descending order
    items.sort(key=lambda x: x[2], reverse=True)
    # Initialize the total value and the remaining weight
    total_value = 0
    remaining_weight = W
    # Iterate through the items
    for item in items:
        # If the item can be included in the knapsack
        if item[1] <= remaining_weight:
            total_value += item[0]
            remaining_weight -= item[1]
    return total_value

# Test the function
assert knapsack_greedy(50, [10, 20, 30], [60, 100, 120], 3) == 220

import java.util.*;

public class KnapsackGreedy {
    public static int knapsackGreedy(int W, int[] weights, int[] values) {
        // Create a list of items with value, weight, and value-to-weight ratio
        List<Item> items = new ArrayList<>();
        for (int i = 0; i < values.length; i++) {
            items.add(new Item(values[i], weights[i]));
        }
        // Sort the items by value-to-weight ratio in descending order
        items.sort((a, b) -> Double.compare(b.ratio, a.ratio));
        // Initialize the total value and the remaining weight
        int totalValue = 0;
        int remainingWeight = W;
        // Iterate through the items
        for (Item item : items) {
            // If the item can be included in the knapsack
            if (item.weight <= remainingWeight) {
                totalValue += item.value;
                remainingWeight -= item.weight;
            }
        }
        return totalValue;
    }

    static class Item {
        int value;
        int weight;
        double ratio;

        Item(int value, int weight) {
            this.value = value;
            this.weight = weight;
            this.ratio = (double) value / weight;
        }
    }

    public static void main(String[] args) {
        // Test the function
        int W = 50;
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        System.err.println(knapsackGreedy(W, weights, values));
//        assert knapsackGreedy(W, weights, values) == 220;
    }
}

Questions:

What can you say about the greedy solution compared to the other solutions?
Now, if you consider the fractional knapsack problem, what would be the greedy solution?

2 — Optimize your solutions

What you can do now is to use AI tools such as GitHub Copilot or ChatGPT, either to generate the solution, or to improve the first solution you came up with! Try to do this for all exercises above, to see the differences with your solutions.

To go further

3 — The fractional knapsack problem

To go beyond

Looks like this section is empty!

Anything you would have liked to see here? Let us know on the Discord server! Maybe we can add it quickly. Otherwise, it will help us improve the course for next year!