Teaching Kids Programming – Using Bottom Up Dynamic Programming Algorithm to Solve 0/1 Knapsack Problem

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?

0/1 Knapsack Problem via Bottom Up Dynamic Programming Algorithm

We can describe the 0/1 Knapsack problem via the following Math terms:

Given a knapsack with capacity and items to pack with weights and values .
We want to pack items into the knapsack subject to total weights not exceeding the capacity.

meaning the quantity of each item we are to pick.
We want to meantime maximize the values .

The Dynamic Programming Equation is:

If the capacity j is enough to pick item i.
Otherwise

We can solve this DP using Top Down Dynamic Programming aka Recursion with Memoization: Teaching Kids Programming – 0/1 Knapsack Problem via Top Down Dynamic Programming Algorithm

Alternatively, we can proactively store the values in a two dimensional array. We need to compute the values of the first row e.g. dp[0][i] for i in range(c). If i (capacity) is larger or equal than the first item’s weight, we can set the value to v[0]. Otherwise, the value gain would be zero.

Then, we start filling the values from the second row up to the last row e.g. dp[n-1].

class Solution:
    def knapsack01(self, weights, values, capacity):
        n = len(weights)

        dp = [[0 for _ in range(capacity + 1)] for _ in range(n)]
        for i in range(capacity + 1):
            dp[0][i] = 0 if weights[0] > i else values[0]

        for i in range(1, n):
            for j in range(1, capacity + 1):
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i] if j >= weights[i] else 0)

        return dp[n - 1][capacity]

The time and space complexity is O(NC) – same as Top Down Dynamic Programming Implementation. However, practically speaking, the Bottom Up Dynamic Programming is faster.

Knapsack Problems

–EOF (The Ultimate Computing & Technology Blog) —

896 words
Last Post: Teaching Kids Programming - 0/1 Knapsack Problem via Top Down Dynamic Programming Algorithm
Next Post: Teaching Kids Programming - 0/1 Knapsack Space Optimised Dynamic Programming Algorithm

The Permanent URL is: Teaching Kids Programming – Using Bottom Up Dynamic Programming Algorithm to Solve 0/1 Knapsack Problem (AMP Version)

0/1 Knapsack Problem via Bottom Up Dynamic Programming Algorithm

Knapsack Problems

Related posts: