Knapsack Problem

Implement a function for the 0/1 Knapsack problem. Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. The solution should not exceed the knapsack's maximum capacity, C.

Your function should take as input:

A list of weights, w[i], representing the weights of each item.
A list of values, v[i], representing the value of each item.
An integer, C, representing the maximum capacity of the knapsack.

The function should return the maximum total value that can fit within the maximum capacity of the knapsack.

Examples


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

weights = [1, 1, 1]
values = [10, 20, 30]
capacity = 2
output: 50

weights = [4, 2, 3]
values = [10, 20, 15]
capacity = 5
output: 35

weights = [4, 5, 1]
values = [1, 2, 3]
capacity = 4
output: 3

The knapsack function solves the 0/1 knapsack problem using a recursive approach with memoization. The function takes as input a list of weights weight, a list of corresponding values values, and a capacity cap. It uses a helper function knapsack_cache that employs a cache to store intermediate results and avoid redundant calculations.

Approach:

Base Cases:
- If there are no items (len(weight) == 0) or if the capacity is zero or negative (cap <= 0), the function returns 0.
- If there is only one item, the function checks if its weight is less than or equal to the capacity. If yes, it returns the item's value; otherwise, it returns 0.
Recursive Case:
- If the weight of the current item (weight[0]) exceeds the capacity, the function recursively calls itself without including this item.
- Otherwise, it calculates two values:
  - added_item_0: the value if the current item is included (current item's value plus the result of the recursive call with the remaining items and reduced capacity).
  - remove_item_0: the value if the current item is excluded (result of the recursive call with the remaining items and the same capacity).
- The function returns the maximum of these two values.
Memoization:
- Before performing any calculations, the function checks if the current state (weight, values, cap) is in the cache. If a match is found, it returns the cached value.
- After computing a new result, it adds the current state and result to the cache.

Solution

import numpy

def knapsack_cache(weight, values, cap, cache):
    for (curr_weight, curr_values, curr_cap, return_val) in cache:
        if numpy.array_equal(curr_weight, weight) and numpy.array_equal(curr_values, values) and curr_cap == cap:
            print("cache called for", weight, values, cap)
            return return_val

    if len(weight) == 0:
        return_val = 0
        cache.append((weight, values, cap, return_val))
        return return_val

    if cap <= 0:
        return_val = 0
        cache.append((weight, values, cap, return_val))
        return return_val

    if len(weight) == 1:
        if weight[0] <= cap:
            return_val = values[0]
            cache.append((weight, values, cap, return_val))
            return return_val
        else:
            return_val = 0
            cache.append((weight, values, cap, return_val))
            return return_val

    if weight[0] > cap:
        return_val = knapsack_cache(weight[1:], values[1:], cap, cache)
        cache.append((weight, values, cap, return_val))
        return return_val

    # include item at 0
    added_item_0 = values[0] + knapsack_cache(weight[1:], values[1:], cap - weight[0], cache)

    # exclude item at 0
    remove_item_0 = knapsack_cache(weight[1:], values[1:], cap, cache)

    return_val = max(added_item_0, remove_item_0)
    cache.append((weight, values, cap, return_val))
    return return_val

def knapsack(weight, values, cap):
    cache = []
    return knapsack_cache(weight, values, cap, cache)

This solution effectively uses memoization to optimize the recursive approach for the 0/1 knapsack problem, ensuring that each state is only computed once and reused when needed, leading to efficient computation in terms of both time and space.

Time Complexity: The time complexity of this approach is $O(n \cdot c)$ , where $n$ is the number of items and $c$ is the capacity. This is because there are $n$ items and up to $c$ different capacity values, and each unique state (combination of remaining items and capacity) is computed at most once due to memoization.

Space Complexity: The space complexity is also $O(n \cdot c)$ due to the cache storing intermediate results for each unique state. Additionally, the recursion depth can go up to $O(n)$ , but this is dominated by the space required for the cache.

Community solutions

💬 Community guidelines

Stay on topic. Use this section for submitting solutions and providing feedback to others.
Be inclusive. Exponent is a diverse community. Please respect others' opinions and beliefs.

How would you answer? Submit your response below and get feedback from the community.

Tiago R.148

November 13, 2024

JavaScript

function knapsack(weights, values, cap) {
    const indicesByValue = Object.keys(weights).map(weight => parseInt(weight));
    indicesByValue.sort((a, b) => values[b]-values[a]);

    const steps = new Map();

    function knapsackStep(cap, sack) {
        if (steps.has(sack)) {
            return steps.get(sack);
        }

        let maxOutput = 0;
        for (let index of indicesByValue) {        
            if (!sack.has(index) && weights[index] <= cap) {
                maxOutput = Math.max(maxOutput, values[index]);

                const remainderCap = cap - weights[index];
                sack.add(index);
                maxOutput = Math.max(maxOutput, values[index] + knapsackStep(remainderCap, sack));
                sack.delete(index);
            }
        }
        steps.set(sack, maxOutput);
        return maxOutput;
    }
        
    let maxOutput = 0;
    for (let index of indicesByValue) {
        if (weights[index] <= cap) {
            maxOutput = Math.max(maxOutput, values[index]);

            const remainderCap = cap - weights[index];
            const sack = new Set([index]);
            maxOutput = Math.max(maxOutput, values[index] + knapsackStep(remainderCap, sack));
        }
    }
    return maxOutput;
}

Jeff S.

Member

161

January 29, 2025

JavaScript

function knapsack(weights, values, cap) {
    if (weights.length === 0 || values.length === 0 || cap === 0) {
        return 0;
    }

    let maxValue = 0;

    function weighKnapsack(knapsack, weight, value, index) {
        if (weight <= cap && value > maxValue) {
            maxValue = value;
        }

        for (let i = index; i < weights.length; i++) {
            if (!knapsack.has(i) && cap >= weight + weights[i]) {
                weighKnapsack(new Set([...knapsack, i]), weight + weights[i], value + values[i], i);
            }
        }
    }

    weighKnapsack(new Set(), 0, 0, 0);
    return maxValue;
}

// debug your code below
const weights = [10, 20, 30];
const values = [60, 100, 120];
const capacity = 50;
console.log(knapsack(weights, values, capacity));

Matthew K.

Member

147

February 19, 2025

JavaScript

function knapsack(weights, values, cap) {
    // your code goes here
    let cache = {}
    function f(n, c) {
        if (c <= 0 || n >= weights.length) return 0

        let cacheKey = `${n}:${c}`
        if (cache[cacheKey]) {
            return cache[cacheKey]
        }

        let result;
        if (weights[n] > c) {
            result = f(n+1,c)
        } else {
            let include = values[n] + f(n+1, c-weights[n])
            let exclude = f(n+1, c)
            result = Math.max(include, exclude)
        }

        cache[cacheKey] = result
        return result
    }
    return f(0,cap)
}

// debug your code below
const weights = [10, 20, 30];
const values = [60, 100, 120];
const capacity = 50;
console.log(knapsack(weights, values, capacity));

Divya R.805

March 23, 2025

public static int knapsack(int[] weight, int[] values, int cap) { int[][] memoized = new int[weight.length+1][cap+1]; for(int i=0; i<=cap; i++) { memoized[0][i]=0; } for(int i=1; i<=weight.length; i++) { for(int currCap=1; currCap<=cap; currCap++) { if(currCap-weight[i-1]>=0) { memoized[i][currCap]=Math.max(values[i-1]+memoized[i-1][currCap-weight[i-1]], memoized[i-1][currCap]); } else { memoized[i][currCap]=memoized[i-1][currCap]; } } } return memoized[weight.length][cap]; }

See community answers

ML Engineer Introduction

ML System Design Questions

Overview

Mock Interviews & Practice Questions

ML Concepts Questions

Overview

Model & Algorithm Fundamentals

Mock Interviews

ML Coding Questions

Overview

Mock Interviews & Practice Questions

Software Engineering Coding Questions

Overview

Fast Track

Time & Space Complexity

Coding Patterns

Arrays

Hash Tables

Searching & Sorting

String Manipulation

Graphs

Trees

Stacks & Queues

Linked Lists

Heaps

Recursion & Backtracking

Dynamic Programming

Behavioral Interviews: A Practical Guide for Engineers

Fast Track (Start Here)

Theory

Tactics

Mock Interviews & Analyses

Practice

ML Engineer Introduction

ML System Design Questions

Overview

Mock Interviews & Practice Questions

ML Concepts Questions

Overview

Model & Algorithm Fundamentals

Mock Interviews

ML Coding Questions

Overview

Mock Interviews & Practice Questions

Software Engineering Coding Questions

Overview

Fast Track

Time & Space Complexity

Coding Patterns

Arrays

Hash Tables

Searching & Sorting

String Manipulation

Graphs

Trees

Stacks & Queues

Linked Lists

Heaps

Recursion & Backtracking

Dynamic Programming

Behavioral Interviews: A Practical Guide for Engineers

Fast Track (Start Here)

Theory

Tactics

Mock Interviews & Analyses

Practice

Examples

Approach:

Solution