這是個求子集合加總問題(subset sum problem)。是算法理論中比較有名的NP問題。
有幾種經典解法:
1.組合論。 有所有集合元素的組合,然後求和與和目標比較。 方法簡單,但算法復雜度高,當集合數較大,比如≥ 15後,速度明顯慢;
2. 動態規劃。遞歸求解,屬於典型的divide and conquer方案。
3. 回溯法(backtracking),子集合屬於這個裏面的壹個特例。 -- 雖然也要遞歸,但相較上面的方法,在集合比較大的時候,也能保持不錯的效率。
下面給出回溯法的vb代碼(vb 2010)。
?Private?Sub?output(ByRef?ta()?As?Integer,?ByVal?ta_size?As?Integer)Dim?ra(ta_size?-?1)?As?Integer?'differ?from?c/c++
Array.Copy(ta,?ra,?ta_size)
Dim?converter?=?New?Converter(Of?Integer,?String)(Function(num)?num.ToString)
Dim?str?=?String.Join("+",?Array.ConvertAll(ra,?converter))
lbSubset.Items.Add(str)
End?SubPrivate?Sub?getSubsetSum(ByRef?sa()?As?Integer,?ByRef?ta()?As?Integer,
ByVal?sa_size?As?Integer,?ByVal?ta_size?As?Integer, ByVal?sum?As?Integer,?ByVal?cnt_node?As?Integer,?ByVal?target?As?Integer)Dim?i?As?Integer
If?target?=?sum?Then
output(ta,?ta_size)
If?cnt_node?+?1?<?sa_size?And?sum?-?sa(cnt_node)?+?sa(cnt_node?+?1)?<=?target?Then
getSubsetSum(sa,?ta,?sa_size,?ta_size?-?1,?sum?-?sa(cnt_node),?cnt_node?+?1,?target)
End?If
Return
Else
If?cnt_node?<?sa_size?And?sum?+?sa(cnt_node)?<=?target?Then
For?i?=?cnt_node?To?sa_size?-?1?'?differ?from?c/c++
ta(ta_size)?=?sa(i)
If?sum?+?sa(i)?<=?target?Then
getSubsetSum(sa,?ta,?sa_size,?ta_size?+?1,?sum?+?sa(i),?i?+?1,?target)
End?If
Next?i
End?If
End?If
End?Sub
Private?Sub?generateSubsets(ByRef?sa()?As?Integer,?ByVal?size?As?Integer,?ByVal?target?As?Integer)
Dim?ta(size?-?1)?As?Integer
Dim?total?As?Integer?=?0
Array.Sort(sa)
total?=?sa.Sum
If?(sa(0)?<=?target)?And?(total?>=?target)?Then
getSubsetSum(sa,?ta,?size,?0,?0,?0,?target)
End?If
End?Sub
Private?Sub?btnStart_Click(sender?As?System.Object,?e?As?System.EventArgs)?Handles?btnStart.ClickDim?size?As?Integer?=?15
Dim?target?As?Integer?=?10
Dim?data()?As?Integer
Dim?i?As?Integer
lbSubset.Items.Clear()
ReDim?data(size?-?1)?'differ?from?c/c++
For?i?=?LBound(data)?To?UBound(data)
data(i)?=?i?+?1
Next?i
generateSubsets(data,?size,?target)
End?Sub