Teaching Kids Programming – 0/1 Knapsack Space Optimised Dynamic Programming Algorithm

ACMer

4 years ago

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given two lists of integers weights and values which have the same length and an integer capacity. weights[i] and values[i] represent the weight and value of the ith item. Given that you can take at most capacity weights, and that you can only take at most one copy of each item, return the maximum amount of value you can get.

Constraints
n ≤ 250 where n is the length of weights and values
capacity ≤ 250

Example 1
Input
weights = [1, 2, 3]
values = [1, 5, 3]
capacity = 5
Output
8
Similar to original knapsack, but how do you ensure the specific element is only included once?

Space-optimised Dynamic Programming Algorithm to Solve 0/1 Knapsack

Given items to pack in a knapsack with capacity . Each item has weight and value . We want to pack the items to gain the maximum value but the total weights from the chosen items should not exceed the knapsack capacity.

Let’s state this mathematically:

We want to maximize the ,
subject to ,
and

When means that we don’t pick the i-th item while means we pack i-th item in the knapsack.

The Dynamic Programming Equation is:

for .

The top down DP uses the Recursion with Memoization aka the magic @cache keyword which asks the computer to remember the intermediate values. The bottom up DP uses two dimensional array dp[i][c] to store the values proactively. For Top Down DP, we call the dp(n-1, c) which will be expanded top down, while the bottom up DP computes the dp[0][0..c] (first row) and then compute the second row dp[1], the third row dp[2] until we get the value dp[n-1][c].

However, dp[i] is based on dp[i-1] only, and thus we can compress the space. That will optimise the space usage from O(CN) to O(C). The inner loop j (capacity) should be inversely enumerated (downwards) to avoid dp[0..j] is overwritten.

class Solution:
    def solve(self, weights, values, capacity):
        n = len(values)
        dp = [0 for _ in range(capacity + 1)]
        for i in range(n):
            for j in range(capacity, weights[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
        return dp[capacity]

class Solution:
    def solve(self, weights, values, capacity):
        n = len(values)
        dp = [0 for _ in range(capacity + 1)]
        for i in range(n):
            for j in range(capacity, weights[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
        return dp[capacity]

The time complexity is still O(CN).

Knapsack Problems

–EOF (The Ultimate Computing & Technology Blog) —

930 words
Last Post: Teaching Kids Programming - Using Bottom Up Dynamic Programming Algorithm to Solve 0/1 Knapsack Problem
Next Post: Teaching Kids Programming - Split String with Same Distinct Counts (Sliding Window)

The Permanent URL is: Teaching Kids Programming – 0/1 Knapsack Space Optimised Dynamic Programming Algorithm (AMP Version)

Space-optimised Dynamic Programming Algorithm to Solve 0/1 Knapsack

Knapsack Problems

Related posts: