Step-by-Step Guide: Dynamic Programming for Subset Sum Problem (Part 2)

This is the Part 2 of my dynamic programming stories. Please also check Part 1.

Contents

Part 1 covered 1, 2 and 3. Part 2 will cover 4 and 5.

1. Given a set of positive integers and a value sum, check if there is a subset of the given set whose sum is equal to the given sum.
2. Given a set of positive integers and a value sum, check how many subsets of the given set whose sum is equal to the given sum.
3. Given a set of positive integers and a value sum, check the minimum number of integers in the subset whose sum is equal to the given sum.
4. Given a set of positive integers and a value sum, check if there is a subset of the given set whose sum is equal to the given sum. Additional condition: Each positive integer pᵢ can be used multiple times.
5. Given a set of positive integers and a value sum, check if there is a subset of the given set whose sum is equal to the given sum. Additional condition: Each positive integer pᵢ can be used at most mᵢ times.

Problem 4

Problem Description

Given a set of N positive integers pᵢ (i = 1, …, N) and a value sum S, check if there is a subset of the given set whose sum is equal to the given sum. Additional condition: Each positive integer pᵢ can be used multiple times.

Example

N = 4, S = 17
p₁ = 8, p₂ = 11, p₃ = 5, p₄ = 6

Correct answer: True (There is a subset whose sum is equal to S.)

Code

import numpy as np

N = 4
S = 17
P = [0, 8, 11, 5, 6] # 0th element is dummy (= not choosing any item).

# dp[i][j] := using the first i items, whether or not we can make the sum j.
dp = np.zeros((N + 1, S + 1), dtype=bool)
# Initialize. We can make the sum 0 by not choosing any item.
dp[0][0] = True

for i in range(1, N + 1):
    for j in range(S + 1):
        if dp[i - 1][j]:
            dp[i][j] = True
        if j >= P[i] and (dp[i - 1][j - P[i]] or dp[i][j - P[i]])):
            dp[i][j] = True
print(f"Answer: {dp[N][S]}")

Please compare this to the code in Problem 1. There is only one difference. The condition of the second if is changed from j >= P[i] and dp[i-1][j-P[i]] to j >= P[i] and (dp[i-1][j-P[i]] or dp[i][j — P[i]]).

Step-by-Step Guide

i = 0: I guess this is already pretty clear. No integer simply means the sum cannot be larger than 0, so dp[0][j] = True only if j = 0.

i = 0

i = 1, 0 ≤ j ≤ 15: This is the same pattern as Problem 1. Please remember dp[1][8] = True because the sum becomes 8 just by adding 8 (= p₁).

i = 1, 0 ≤ j ≤ 15

i = 1, j = 16: Here you can see the difference between Problem 1 and Problem 4. If we use 8 once, we can’t make a subset (sum = 16), but by using 8 twice, we can make such a subset.

Then how do you implement this in the code? The key is dp[i][j — P[i]]. In the current case, dp[1][16] = True because dp[1][16 — 8] = dp[1][8] = True and we add another 8 to the subset.

To generative this, dp[i][j] is equal to True if one of these three conditions is satisfied.

Condition 1: dp[i-1][j] = True
Condition 2: dp[i-1][j-P[i]] = True
Condition 3: dp[i][j-P[i]] = True

i = 1, j = 16

The rest will be very similar, so I will not write details.

The rest

But you may have noticed that we can omit one of the three conditions. Which one is it?

For a positive integer k, dp[i][k] is always True if dp[i-1][k] is True. This means. For example, if k is equal to 0, then both dp[0][0] and dp[1][0] are True.

Actually, Condition 1 guarantees this, leading to this fact that if Condition 2 is True, then Condition 3 is True too. Therefore we don’t really need to check if Condition 2 is True or not.

This is the code snippet without Condition 2.

for i in range(1, N + 1):
    for j in range(S + 1):
        if dp[i - 1][j]:
            dp[i][j] = True
        if j >= P[i] and dp[i][j - P[i]]:
            dp[i][j] = True

Writing in this way is also possible.

for i in range(1, N + 1):
    for j in range(S + 1):
        dp[i][j] = dp[i - 1][j] or (j >= P[i] and dp[i][j - P[i]])

Problem 5

Problem Description

Given a set of N positive integers pᵢ (i = 1, …, N) and a value sum S, check if there is a subset of the given set whose sum is equal to the given sum. Additional condition: Each positive integer pᵢ can be used at most mᵢ (i = 1, …, N) times.

Example

N = 4, S = 17
p₁ = 4, p₂ = 7, p₃ = 5, p₄ = 6
m₁ = 2, m₂ = 1, m₃ = 1, m₄ = 2

Correct answer: There is a subset whose sum is equal to S.

Code

import numpy as np

N = 4
S = 17
P = [0, 4, 7, 5, 6] # 0th element is dummy (= not choosing any item).
M = [0, 2, 1, 1, 2] # 0th element is dummy.

# dp[i][j] := using the first i items, if the sum is equal to j, how many of the i-th item is still available.
#             -1 means cannot make the sum j
dp = np.zeros((N + 1, S + 1), dtype=np.int8)
dp.fill(-1)
# Initialize. We can make the sum 0 by not choosing any item.
dp[0][0] = 0

for i in range(1, N + 1):
    for j in range(S + 1):
        if dp[i - 1][j] >= 0: ## Condition 1
            # We can make the sum j without using the i-th item.
            dp[i][j] = M[i]
        elif j >= P[i] and dp[i][j - P[i]] > 0: ## Conditon 2
            # We can make the sum j by using the i-th item.
            dp[i][j] = dp[i][j - P[i]] - 1
        else: ## Otherwise
            # We cannot make the sum j without using the i-th item.
            dp[i][j] = -1
        
print(f"Answer: {dp[N][S] >= 0}")

Here the definition of dp differs largely.

Using the first i items, if the sum is equal to j, how many of the i-th item is still available. -1 means cannot make the sum j.

Let’s see how this code works one by one!

Step-by-Step Guide

If i = 0, there are two cases.

j = 0: We can create a subset and don’t have any remaining integers, so the value is 0.
j > 0: We cannot create a subset, so the value is -1.

i = 0

Let’s move to i = 1. Do you understand why j = 0 is 2? It’s because we can make sum = 0 without using p₁ and we can still use p₁ two more times (= m₁ = 2).

i = 1, j = 0

Then we can intuitively know that the sum of subset {p₁} is equal to 4 and the sum of subset {p₁, p₁} is equal to 8.

In other words, if j = 4, we can use p₁ one more time (dp[1][4] = 1). Also, if j = 8, there is no stock for p₁ (dp[1][8] = 0).

i = 1, j ≥ 1

Let’s think how we can make logic for our code.

[Condtion 1] At first, we have to check whether or not dp[i-1][j] is non-negative. If the value is non-negative, we don’t have to use pᵢ at all, so dp[i][j] is equal to mᵢ. In this example, dp[0][0] is a non-negative value, so dp[1][0] is equal to 2 (= m₁).

[Condition 2] Next, check whether dp[i][j-P[i]] is positive. If the value is positive, we can use one pᵢ to create a subset whose sum is j. For example, dp[1][0] is equal to 2, so dp[1][4] is 1 (= 2–1). dp[1][8] works in the same way. dp[1][8] is equal to 0, which is dp[1][4] — 1 .

Finally, if neither Condition 1 nor Condition 2 is satisfied, dp[i][j] is -1, meaning we can’t make such a subset. We already finished using p₁ when j = 8, which is shown as dp[1][8] = 0. When we come to j = 12, dp[1][12–4]=dp[1][8] is not positive, so we assign -1 to dp[1][12].

i = 1

i = 2: We can update this row in the same way.

Red circle + solid line: Condition 1
Blue circle + dashed line: Condition 2

i = 2

In the end, dp becomes like this below.

To find the solution of this problem, we can check the value of dp[N][S], which is dp[4][17]. If the value is non-negative, we can create a subset. If the value is -1, we cannot create a subset.

In this case, since dp[4][17] = 1, we can say there is a subset whose sum is 17.

The rest