這次我想給大家分享的內(nèi)容是動態(tài)規(guī)劃Subset Sum (子集之和)問題 。其實(shí)挺枯燥的，涉及到的是數(shù)學(xué)和編程方面的內(nèi)容，如果不感興趣請直接退出閱讀。
本文概要:
- Subset Sum 問題描述
- 問題求解思路
- 遞歸法求解
- 重點(diǎn)：動態(tài)規(guī)劃法求解
Subset Sum 問題
假設(shè)有一串 { 1,2, 4,5,6} , 是否存在任意數(shù)字之和為 7 ， 55 。
通過目測 { 1, 2,4} {5, 2} 之和為7，所以答案為存在，因?yàn)樗性刂托∮?5，所以答案為不存在。
問題:
假設(shè)有一個非負(fù)整數(shù)的集合 Set ,求是否存在一個組合使得其中任意元素之和為一個給定的整數(shù) sum ？
A = { X1,X2,....Xn}, sum = Y
subset(A,Y) = True or False ?
求解思路
我們立馬能想到第一個方法是先求解集合A 所有的排列組合，一共有2的5次方種可能，然后逐一對組合求和判斷是否等于6。這種思路屬于暴利求解法，當(dāng)集合元素非常多的時候，計(jì)算時間會指數(shù)級增長，該算法的時間復(fù)雜度為O(2^n)。
第二種求解方法的思想是 把大事化小，小事化無的。
如： A = { 1,2, 4,5,6} 可以簡化為 { 2, 4,5,6 } 這個子集合元素是否有sum = 6 的解，或者{ 2, 4,5,6 } 是否存在相加之和為5 的解 。依次類推可以將問題一層一層縮小，利用上篇文章提到的遞歸思想。
遞歸求解法
arr = [1,2 ,4,5,6]
def subset(arr , i , s):
if i == 0:
return s == arr[0]
elif s == 0:
return True
elif arr[i] > s :
return rec_subset(arr, i-1 , s)
else:
A = subset(arr , i-1 ,s - arr[i])
B = subset(arr, i-1 , s)
return A or B
print( subset(arr ,len(arr )-1, 7))
out: True
通過遞歸方式來求解必須遍歷所有的子問題，但其中子問題有重疊的部分，也就是說存在重復(fù)計(jì)算的情況，算法時間復(fù)雜度為O(2^n)。對于規(guī)模比較大的問題這是無法容忍的。接下來通過動態(tài)規(guī)劃的方法 ，來避免重復(fù)計(jì)算來優(yōu)化程序的性能。
動態(tài)規(guī)劃求解法
動態(tài)規(guī)劃是從下往上(bottom-up)的求解方法，并且把中間結(jié)果緩存起來避免重復(fù)計(jì)算。
例如：把{ 1,2, 4,5,6} 分解成 空集 0 { } ,1 { 1 } ，2 { 1,2 } ,3 { 1,2, 4 }, ,4 { 1,2, 4,5 } ,5 { 1,2, 4,5,6} 分別來計(jì)算，具體流程如下。
- 構(gòu)建一個二維數(shù)組Subset[i,j] 來存放子集合相加和的所有可能情況，True（以下記為T）表示存在解，F(xiàn)alse(以下記為F)表示不存在解。
如圖1: 行為子集相加為0-7所有的情況，列為0-5個元素的所有情況。
第一行表示： 除了第一列為0存在解標(biāo)記為T 之外，其余1-7都為 F 。
第一列表示：各個子集相加之和為0的情況。例如 {1 } 的情況顯然如果 不取元素1 空集{}之和存在0的解，類似{1，2} 也有存在0的解，因此第一列都為T。
第二行第二列：表示{1} 之和為1，顯然為T 。
第二行其余列：因?yàn)樽畲鬄?，所以余下都為F。
中間任意一個格子計(jì)算方法，分兩種情況。
如果格子上方為T，當(dāng)前格子也為T。實(shí)際意義為：當(dāng)前集合的子集如果有解那么，當(dāng)前集合也有解，如{1，2，4} 之和3的情況，因?yàn)?{1，2} 存在之和為3的解。
因此得出結(jié)論，只要T下方的格子都可以設(shè)置為T。
如果格子上方為F, 則求 sum - A 余下子集合的解。例如上圖綠色標(biāo)記的位置 Subset[2,4] , 可以簡化為求解 { 1 } 是否有 1的解，查表值為T，當(dāng)前表格值則 為T。
用此算法，把表格填滿。
表格最后一個元素就是 { 1,2, 4,5,6} 是否存在子集合之和為7 這個問題的解。
具體的代碼實(shí)現(xiàn):
import numpy as np
def dp_subset(arr,S):
subset = np.zeros((len(arr),S+1),dtype=bool) #構(gòu)造二維數(shù)組
subset[:,0] = True # 第一列 設(shè)為True
subset[0,: ] = False #第一列 設(shè)為 False
subset[0,arr[0]] = True
for i in range(1,len(arr)):
for s in range(1, S+1):
if arr[i] > s:
subset[i , s] = subset[i-1 , s]
else:
A = subset[i-1 , s ]
B = subset[i-1 , s - arr[i]]
subset[i,s] = A or B
row ,cell = subset.shape
return subset[row-1,cell-1]
arr = [1,2, 4,5,6]
dp_subset(arr,7)
out:True
