The 0/1 Knap-sack Problem
Tags: programming, algorithms
Published: 2024-02-29 05:53:50

## 1. Overall Idea
The sub-problem:
If we're given the optimal solution for `item[0]...item[i]` with a bag of size `n`, when facing `item[i+1]`, we only have to think about two things:

1. If we must add `item[i+1]` of `weight[i+1]` and `value[i+1]`, then the total value is:
**(optimal solution for `item[0]...item[i]` with a bag of size `n-weight[i+1]`)** + **(`value[i+1]`)**
2. See if not including `item[i+1]` yields a higher value, in other words, check **optimal solution for `item[0]...item[i]` with a bag of size `n`**

Therefore, it's clear to see that we define the sub-problem as a two-dimension memoization, where:

- `dp[i][j]` = the optimal solution for the first `i` items with a bag of size `j`
- `dp[i][j+1]` = the higher of `dp[i-1][j+1]` and `dp[i-1][j-weight[i]] + value[i]` 

## 2. The Classic Approach

We first init a 2D array, where `row[i] = item[i]` and `col[i] = bag of size i`.

Populate the base cases of "empty bag with all items" and "first item with bag of all sizes"
```
dp = int[item_len][bag_size + 1]
for i in range(0, item_len): 
    dp[i][0] = 0
for i in range(0, bag_size + 1): 
    dp[0][i] = values[0] if i >= weights[0] else 0
```

Applying the sub-problem induction logic, note that we need to start from the second row and second column in each row.
```
for i in range(1, item_len):
    for j in range(1, bag_size + 1):
        if weights[i] > j: # item too big
            dp[i][j] = dp[i - 1][j]
        else:
            add_item = dp[i - 1][j - weights[i]] + values[i]
            skip_item = dp[i - 1][j]
            dp[i][j] = max(add_item, skip_item)
```

- Space Complexity: `O(bag_size * item_len)`
- Time Complexity: `O(bag_size * item_len)`

## 3. Space-Optimised Approach

In the previous approach, we used a 2D array to store the computed results in our DP but we can observe one thing that to compute the result for `item[i]` we just need the results for `item[i-1]`.

Therefore, we can reduce the size of our DP to 1D by just storing the results on different bag sizes for the previous element.

```
dp = [0] * (bag_size + 1)
for i in range(0, bag_size + 1):
    if weights[0] <= i: dp[i] = values[0]
    
for i in range(1, size):
    for j in range(1, bag_size + 1):
        if weights[i] > j:
            dp[j] = prev[j]
        else:
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

print(memo[bag_size])
```
- Space Complexity: `O(bag_size)`
- Time Complexity: `O(bag_size * item_len)`


## 4. The "Forward-Thinking" Approach (Intuitive)

In all previous approaches, we think in the way of "if I add the current item(of weight `w`) into my bag(of size `n`), I must trace back to find the optimal solution for bag size of `n-w` in order to calculate the new total value".

This is a form of back-tracking, using "backward thinking".

Another way to think about this could be "if I add the current item(of weight `w`) into my bag(of size `n`), it will produce a new solution(not necessarily optimal) for bag size of `n+w`, given the optimal solution for bag size of `n`"

This is more like "forward-thinking", which is actually just the same logic, but we will now use a hashmap instead of an array to store the intermediate results, and each key-value pair of the hashmap now has a slightly different meaning than the array approach:

- each key of the hashmap is an integer in range `[0, bag_size]`
- each value of key `n` marks the optimal solution for a bag that has items with total size of exactly `n`

```
# an empty bag has maximum value of 0
dp = {0: 0}

for i in range(0, item_len):
    prev = dict(dp)
    for size in prev:
        new_size = size + weights[i]
        if new_size <= bag_size:
            if new_size in prev:
                dp[new_size] = max(prev[new_size], prev[size] + values[i])
            else:
                dp[new_size] = prev[size] + values[i]

print(max(dp.values()))
```

Note that we cannot simply return `dp[bag_size]` as the final solution with this approach, since:
1. There might not be a combination of items that gives a total weight of exactly `bag_size`
2. The optimal solution might come from a key that is less than `bag_size`

- Space Complexity: `O(bag_size)`
- Time Complexity: `O(bag_size * item_len)`

## 5. The Target Sum Problem

> Given an array of positive integers `nums`, and an integer `target`, return `True` if there is a subset of `nums` such that the sum of its elements is equal to `target`, return `False` otherwise. 
Example: `nums = [1,2,3,3]`, `target = 7` will return `True` (`[1,3,3]`)

We could solve this problem with the classic knap-sack approach, where `target` is the bag size, and each number `x` in `nums` can be regarded as an item of weight `x` and value `x`, then at the end we simply return `dp[target] == target`

```
dp = [False] * (target + 1)
dp[0] = True

for num in nums:
    for i in range(num, target + 1):
        dp[i] = dp[i] or dp[i - num]

return dp[target_sum]
```

However, it's also interesting to follow the "forward thinking" approach:
- we loop through each number in `nums`
- at each number `n`, we keep a list of all possible sums so far `sums`, and add in the new sums produced by `n+sums[i]`

An example using hashmap
```
possible_sums = {0: True}

for n in nums:
    prev = dict(possible_sums)
    for s in prev:
        if s + n <= target: possible_sums[s + n] = True

return (target in possible_sums)
```
Note that the only difference here is that we change the order in which to find the solution, from "looking back" to "looking forward". However, by turning it to "forward thinking", it now feels more linear and straight forward.

I often find it useful to take the "forward-thinking" approach for many other knapsack-like problems.

## Conclusion
In this blog, I compared the classic approach, space-optimised approach and forward-thinking approach of solving the 0/1 knap-sack problem, as well as showing how the forward-thinking approach could give us another subtle way to view and understand the knap-sack problem, by solving another similar problem "Target Sum".

All of these approaches are essentially the same strategy using dynamic programming, but I hope that by giving a side-by-side comparison here, it can help us build a more thorough understanding of the knapsack problem and the idea behind dynamic programming.