| FazBrowse GitHub Viewer | Trending | | Home |
| Tools: [Download Repo ZIP] [Original HTTPS Page] |
| Name | Name | Last commit date | ||
|---|---|---|---|---|
parent directory.. | ||||
| layout | post |
|---|---|
| title | (Dynamic Programming) Subset Sum |
给定一个包含数字的矩阵A和一个数字B，找出矩阵A中是否可以有数字相加得到数字B。
假设我们的矩阵是[2, 3, 7, 8, 10]，数字B是11，下面给出分析步骤。
我们先画出初始表格如下
| 矩阵 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | T | |||||||||||
| 3 | T | |||||||||||
| 7 | T | |||||||||||
| 8 | T | |||||||||||
| 10 | T |
因为0只需我们不找任何数字就可以得到，所以那一列都为True。
接下来，我们来看数字2这一行。
| 矩阵 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | T | F | T | F | F | F | F | F | F | F | F | F |
| 3 | T | |||||||||||
| 7 | T | |||||||||||
| 8 | T | |||||||||||
| 10 | T |
由于只有一个数字2，所以只有2这一列是True
然后，我们看数字3这一列（此时，我们同时拥有数字2和3）
| 矩阵 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | T | F | T | F | F | F | F | F | F | F | F | F |
| 3 | T | F | T | T | F | T | F | F | F | F | F | F |
| 7 | T | |||||||||||
| 8 | T | |||||||||||
| 10 | T |
此时，有两种情况： 1. 如果走到的列小于数字3，我们就直接取上一行同列的值，比如走到1或者2时 2. 如果走到的列大于等于数字3，此时，如果上一行同列是True，就直接取True，否则，还要去看上一行中减去3那一列的值。 例如，如果此时走到了5，因为上一行该列为False，我们就爱要看上一行中列为2的值(5 - 3)，为True
以此类推，得到最终的表格如下
| 矩阵 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | T | F | T | F | F | F | F | F | F | F | F | F |
| 3 | T | F | T | T | F | T | F | F | F | F | F | F |
| 7 | T | F | T | T | F | T | F | T | F | T | T | F |
| 8 | T | F | T | T | F | T | F | T | T | T | T | T |
| 10 | T | F | T | T | F | T | F | T | T | T | T | T |
得出转移方程
if j < input[i]:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - input[i]]
class Solution():
def do(self, arr_input, sum_num):
len_arr = len(arr_input)
dp = [[True] * (sum_num + 1) for _ in range(len_arr)]
for i in range(len_arr):
for j in range(1, sum_num + 1):
if i == 0:
if arr_input[i] != j :
dp[i][j] = False
else:
if arr_input[i] > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - arr_input[i]]
return dp[-1][-1]
solution = Solution()
print solution.do([2, 3, 7, 8, 10], 11)| Back | FazBrowse Home | New Git URL |