#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/knapsack/knapsack-2-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/knapsack/knapsack-2-implementation

Repovive

Knapsack 2 - Implementation - Knapsack | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

Knapsack 2 - Implementation

The code

V_max = sum of all values
dp[0] = 0, dp[v] = infinity for v > 0

for i from 1 to n:
    for v from V_max down to value[i]:
        dp[v] = min(dp[v], dp[v - value[i]] + weight[i])

answer = largest v where dp[v] <= W

Time: $O(n \cdot V_{max})$ . With $n = 100$ and $V_{max} = 100{,}000$ , that's $10^7$ operations.

Space: $O(V_{max})$ using 1D array.