DEV Community: Alex Kang

Dynamic Programming: Knapsack

Alex Kang — Tue, 16 Aug 2022 01:41:31 +0000

What is Knapsack?

There are many ways to describe the problem, but my favorite is to describe it as a thief robbing a store:

Imagine a thief robbing a store with a bag of some capacity. The thief sees many items, and each item has a different value and weight. If he can only take one of each item, which items should he take to maximize his profit?

Understanding the problem

What are some ways to solve this problem?

At first glance, the knapsack problem seems as if a greedy approach would be suitable. But, a greedy approach does not guarantee an optimal solution.

Let's look at a case where the greedy approach does not find an optimal solution.

Item	Weight	Value	Value/Weight
A	3	16	5.33
B	2	10	5
C	2	10	5

Let's solve the problem for a capacity of 4.

Using the greedy approach, we would take item A since it has the highest value-weight ratio. After we take item A, we won't have space for other items.

But the optimal solution is to take items B and C.

This counterexample shows that the greedy approach is not always optimal.

Can we solve knapsack with dynamic programming? Does the problem have the two dynamic programming properties?

Solving 0/1 Knapsack

In the previous post we discussed that to solve dynamic programming problems, you need:

the problem defined as relatable subproblems

recurrence relation to relate the sub-solutions to the original solution

base cases for the recurrence relation

1. Problem as relatable subproblems

Let's identify the dynamic programming characteristics of the problem. Then, we can check if we can use dynamic programming.

Defining subproblems

In the knapsack problem, we can choose to take or leave the item if the item fits into our knapsack. We need two variables to identify each choice (subproblem): the item index and the remaining capacity.

Variable definitions:
i: item index
rc: remaining capacity
i_weight: current item weight
i_val: current item value

We can define the subproblems to be state(i, rc). The collection of subproblems is all instances of state(i, rc) where 0 <= i < num_items and 0 < rc <= total_capacity. The solution to each subproblem is the maximum profit at state(i, rc).

Optimal substructure

Can we construct the solution to state(i, rc) using smaller subproblems?

At item i, we have two choices: to include i, or to exclude i. If we choose to exclude i, the solution does not change from the previous item. If we choose to include i, we need to make room for the item weight and include the item. The larger of the two is the solution to state(i, rc)

Solution to state(i, rc) is the maximum of:

state(i-1, rc) (exclude item i)
state(i-1, rc-i_weight) + i_val (include item i)

We can use smaller subproblems to find the optimal solution.
So, the problem has the optimal substructure property.

Overlapping subproblems

We need to calculate the subproblems state(i-1, rc) and state(i-1, rc-i_weight) + i_val in almost every state.

So, the problem has the same subproblems, and the problem has the overlapping subproblems property.

2. Recurrence relation

We already found the recurrence relation above!

...maximum of:

state(i-1, rc) (exclude item i)

state(i-1, rc-i_weight) + i_val (include item i)

Finding the recurrence relation is usually the hardest part of the problem.
Here are some tips for finding the recurrence relation:

How can we use smaller subproblems to solve larger subproblems?
Does the problem ask for the min/max of something? If so, the recurrence relation is often the min/max of a subset of subproblems.

3. Base cases for the recurrence relation

When the problem is about finding the min/max of something, the base case value is usually 0.

The base case is:

When i or rc is out of range, we return 0.

Top-down approach

A simple way to think about the top-down approach is "DFS + memoization". If we do not need to solve all subproblems linearly, a top-down approach can be more efficient than a bottom-up approach

The three important parts are:

function to solve a single subproblem
DFS to traverse through the state-space tree
data structure for memoization
recurrence relation to relate the subproblems
base cases for the recurrence relation

Here is a solution with comments using python.

Time complexity for top-down approach

Time complexity: O(NM) where N = num_items, M = capacity.
Space complexity: O(NM) where N = num_items, M = capacity.

Bottom-up approach V1

A simple way to think about the bottom-up approach is filling out the table. The bottom-up approach does not use recursion, so there is no recursion overhead.

The important parts are

table to keep to store solutions to subproblems (dimension = num_variable in each state)
loop to fill out the table
recurrence relation to relate the subproblems
base cases for the recurrence relation

Here is a solution with comments using python.

Time complexity for bottom-up approach V1

Time complexity: O(NM) where N = num_items, M = capacity.
Space complexity: O(NM) where N = num_items, M = capacity.

Bottom-up approach V2

Can we reduce the space complexity?

In the recurrence relation, we only access the previous and current row. We can use just two rows to solve knapsack.

Here is a solution with comments using python.

Time complexity for bottom-up approach V2

Time complexity: O(NM) where N = num_items, M = capacity.
Space complexity: O(M) where M = capacity.

Bottom-up approach V3

Can we reduce the space complexity even more?

In the recurrence relation, we access the previous and current row. But, we only access columns to the left of the previous row. If we iterate the columns from the right, we can use a single row to solve knapsack.

Time complexity for bottom-up approach V3

Time complexity: O(NM) where N = num_items, M = capacity.
Space complexity: O(M) where M = capacity.

Comparing different methods

To test my algorithms, I used the 8 test cases from here. Test 8 is a fairly large test case where num_item = 24 and capacity = 6404180.

For fun, here is the execution time of each versions of knapsack.

Knapsack function	Execution time
Top-down	5.599s
Bottom-up v1	33.246s
Bottom-up v2	25.293s
Bottom-up v3	19.063s

The reason why the top-down approach is so fast is that the weights(each 6 digits) and the capacity(7 digits) are large.

In this case, calculating for every single capacity is an overkill, since all weight values are 6 digits long.

The difference between the execution time of the bottom-up approaches is most likely from:

creating different array sizes
different number of conditionals
unknown compiler optimizations

Let me know if you have any other ideas!

Conclusion

Knapsack is a classic, but not an easy dynamic programming question. To solve dynamic programming questions, we need to identify the dynamic programming characteristics. When we identify them, we can find how the subproblems relate, and eventually lead to the recurrence relation.

Dynamic Programming in Python

Alex Kang — Fri, 12 Aug 2022 07:01:00 +0000

What is dynamic programming?

Dynamic programming is a technique that allows us to solve a class of problems with overlapping subproblems and optimal substructure.

Dynamic programming is also a technique that trades space for time. With dynamic programming, a problem with exponential number of subproblems can often be solved in polynomial time.

The time complexity of dynamic programming problems is usually O(MN), where M = number of subproblems, N = time complexity of subproblems.

Characteristics of dynamic programming

Overlapping subproblem: the original problem has multiple instances of the same subproblem.

Optimal substructure: the solution to the original problem can be constructed from solutions of subproblems.

Dynamic programming implementations

The two dynamic programming implementations are:

top down (DFS + memoization)
bottom up (tabulation

To solve dynamic programming problems, you need:

the problem defined as relatable subproblems
recurrence relation to relate the sub-solutions to the original solution
base cases for the recurrence relation

Common dynamic programming questions

Here are 6 common dynamic programming questions:

Knapsack
Longest increasing subsequence
Longest common subsequence (edit distance)
Matrix chain multiplication
Kadane's algorithm
Distinct Ways

Building a Second Brain

Alex Kang — Fri, 12 Aug 2022 05:22:05 +0000

Building a Second Brain: A Proven Method to Organize Your Digital Life and Unlock Your Creative Potential, by Tiago Forte

I am personally not a fan of self-improvement books. Their advice sounds nice and sounds motivating, but in reality, it's really difficult to integrate the advice because it's out of context.

This book is different because it teaches you a systematic way (the second brain) to apply that knowledge in your life.

I'm not a note taker; it's harder to concentrate, and I barely ever looked at them. Plus, it takes forever to find the information you need even if you have all the notes in the world.

Despite not liking note-taking, I found some great takeaways from this book that I want to incorporate into my life.

Takeaways

Externalizing our thoughts makes them more concrete
Organize our digital archive by "how actionable", not "what kind of info"
Discoverability of info decreases as the amount of note-taking increases
Distillation of notes increases discoverability

The author shares an amazing organization system called PARA, which stands for

P: Projects (short-term goals you are working on)
A: Areas (generalized long-term goals)
R: Resources (future references)
A: Archives (completed or inactive)

I organized my notes into PRA (without the 'Areas'), something like this:

├── Project/
│   ├── Project1/
│   │   ├── somefile
│   ├── Project2/
│   │   ├── somefile
├── Resources/
│   ├── Topic1/
│   │   └── somefile
│   ├── Topic2/
│   │   └── somefile
└── Archives/
    └── archivefile

Conclusion

This book is a great read and contains a lot of information on how you can organize the massive amount of information you consume every single day. With the abundance of information, it has been harder to keep track of what we know and what we need. If you want to hear a solution to that problem, give this book a read!

Binary Search Templates in Python

Alex Kang — Fri, 12 Aug 2022 05:14:00 +0000

What is Binary Search?

Binary search is a search algorithm that divides the search interval by half every time. That also means that the time complexity of binary search is O(log n)

Templates

Binary search can:

find single element in a sorted array
find first index satisfying a condition

Find single element in a sorted array

def binary_search(arr, target):
    left, right = 1, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        elif arr[mid] > target:
            right = mid - 1
        else:
            return mid
    return -1

Find first index satisfying a condition

Finding the first index satisfying a condition is the same as finding the first true value of a true-false array.
ex: [False, ... False, True, ... True]

Things to note:

left and right should include and read & write space
while loop halts when left == right
after the while loop:
- left is the first index satisfying condition() == True
- left - 1 is the last index satisfying condition() == False

def condition():
    pass

def binary_search(arr):
    left, right = 1, len(arr)-1
    while left < right:
        mid = (left + right) // 2
        if condition():
            right = mid
        else:
            left = mid + 1
    return left

Two Pointers Templates in Python

Alex Kang — Fri, 12 Aug 2022 04:46:00 +0000

What is two pointers technique?

Two pointer technique is using two pointers in an array to solve problems efficiently.

Templates

3 common two pointers techniques are:

Sliding window
Pointers from two ends
Fast and slow pointers

Sliding Window

Sliding window can be used to search something in a subarray.

def get_counter():
    pass

def condition():
    pass

def do_something_before():
    pass

def do_something_after():
    pass

def sliding_window(arr):
    counter = get_counter()
    # outer loop to move end index
    while end < len(arr):
        end += 1
        # start index only increase when condition
        while condition():
            do_something_before()
            start += 1
    do_something_after()

Pointers from two ends

Pointers from two ends can be used when the problem can be reduced to finding two elements in an array that satisfy a condition.

def condition_left():
    pass

def condition_right():
    pass

def do_something():
    pass

def pointers_from_two_ends(arr):
    left, right = 0, len(arr)-1
    while left < right:
        if condition_left():
            left += 1
        if condition_right():
            right -= 1
        do_something()

Fast and slow pointers

Fast and slow pointers can be used to:

detect cycles
remove duplicates
find middle node

def condition_slow():
    pass

def do_something():
    pass

def fast_slow_pointers(arr):
    slow = 0
    for fast in range(len(arr)):
        # only move slow pointer when condition
        if condition_slow():
            slow += 1
        do_something()

DFS Templates in Python

Alex Kang — Fri, 12 Aug 2022 04:10:00 +0000

What is DFS?

Depth-first Search (DFS) is a tree/graph traversal algorithm that explores as far as possible in each branch.

DFS traversal of the tree above would be:
[0, 1, 3, 4, 2, 5 ,6]

DFS applications

Some of the applications of DFS are:

traversing a explicit tree to find something
traversing a graph to:
- find topological sort of graphs
- cycle detection in graphs
- find spanning trees
use backtracking to:
- solve puzzles
- solve combinatorial problems

Templates

We can simply traverse through the tree/graph using the following templates.

DFS on binary tree



def do_something(root):
        pass

def dfs(root):
    if not root:
        return
    do_something(root)
    dfs(root.left)
    dfs(root.right)

DFS on N-ary tree



def do_something(root):
    pass

def get_children(root):
     pass

def dfs(root):
    if not root:
        return
    do_something(root)
    for child in get_children(root):
        dfs(child)

DFS on graphs



visited = set()
def do_something(root):
    pass

def get_neighbors(root):
    pass

def dfs(root, visited):
    if root in visited:
        return
    do_something(root)
    visited.add(neighbor)
    for neighbor in get_neighbors(root):            
        dfs(neighbor, visited)

In addition to simple traversals, we can also pass value up from child to parent (using return value) or pass value down from parent to child (using function parameters).

Example of passing value up (return value)

Finding max depth of N-ary tree



def get_children(root):
    pass

def max_depth(root):
    if not root:
        return 0
    depth = 0
    for child in get_children(root):
        depth = max(depth, max_depth(child))
    return depth + 1

Example of passing value down (function parameter)

Print path on a binary tree



def dfs_path(root, res):
    if not root:
        return
    res.append(root)
    dfs_path(root.left, res)
    dfs_path(root.right, res)

Backtracking is also a variation of DFS. Backtracking does not explore the whole tree/graph. Instead, backtracking stops exploring branches that cannot lead to a solution.

Backtracking can often be used to solve puzzles or combinatorial problems.

Backtracking template



def condition():
    pass

def do_something(root):
    pass

def get_children(root):
     pass

def backtrack(root):
    if not condition():
        return
    do_something(root)
    for child in get_children(root):
        backtrack(child)

My Internship Experience

Alex Kang — Wed, 10 Aug 2022 03:02:24 +0000

Hi, I'm a beginner on a software development journey with a passion for learning and development. Back in 2020, I was fortunate enough to intern with an amazing team of developers. Since then, I have been temporarily serving in the mandatory military in my country.

Internship Experience

The team that I was assigned to was responsible for developing and running messaging services in a microservice architecture.

The team lead was my mentor, and he described briefly what microservices were and what their team was responsible for. My mentor often took extra time to explain more about the architecture and why the team made each design choice.

My first job was to get familiar with the code base. Luckily, the team had some deprecation work. While I was doing deprecation work, I made my first ever pull request and also my first ever contribution to production code. I was also able to experience a little bit of DevOps by making sure that the pipeline ran successfully.

After I got familiar with the code base, I was given a chance to code a message exchange interchange, which was responsible for delivering messages from source to destination in a microservices architecture. It was a lot of fun working with them and seeing my contributions deployed to production.

Our team decided to migrate from Bitbucket and Jfrog Pipelines to Github and Azure Pipelines. I was also able to learn about CI/CD and experiment with various technologies.

One of our team members was in charge of migrating the SFTP server from Sterling File Gateway to AWS. It was expected that running the server on AWS would be almost half the cost of the Sterling File Gateway. I worked on researching if certain things were available in AWS, and I also worked hands-on with AWS labmda for POC of the migration.

Conclusion

I have learned so much in my short internship. Even th

ough I was not able to dive deeper into the concepts and technologies that I worked with, I am extremely grateful that I was exposed to so many important concepts that were not taught in school.

Before my internship, I thought programming was all about algorithms, data structures, networking, and databases. My internship opened my eyes to a whole new world of software development. I am excited about my journey to learn more and become a better software developer.

How to Solve it

Alex Kang — Wed, 10 Aug 2022 00:41:00 +0000

I have always wanted to become better at problem-solving, but I never had a concrete plan on how I could be better.

I came across "How to Solve It" by G. Polya, written in 1945 by a mathematician who gave 4 simple steps to solve any type of problem.

1. Understand the problem

This step seems so trivial, but it is also easy to neglect the importance of it because it is trivial. I personally have tried to solve problems without fully understanding them. I wasted many hours developing a solution that did not solve the initial problem, or missed an easier way to solve the problem.

To make sure you understand the problems, ask yourself:

Do you understand all the words in the problem?
Can you restate the problem?
Can you visualize the problem?
What is the unknown?
What is known?
What is the connection between the known and the unknown?

2. Devise a plan

When we understand the problem, we need to come up with a plan to find the unknown. This step may take a long time!

To come up with a plan, ask yourself:

Do you know a related problem? Can you use it?
Can you solve a related or smaller problem?

3. Carry out the plan

Carrying out the plan is much easier than devising a plan.

While carrying out your plan, you should check each step. If the plan does not work, go back to devising a plan.

4. Look back

After you have solved the problem, it is important to look back and examine the solution.

Ask yourself:

Can you check the result?
Can you derive the solution differently?
Can you use the solution for some other problem?

Conclusion

Even though the steps are somewhat obvious, we often neglect these steps. I have known these steps for a while now, but I still don't spend enough time on the first two steps, just out of laziness or impatience. But in the end, lack of planning almost always leads to disaster. Follow these steps and focus on the first two steps to become better at problem solving.