-1
假設你有一些元素,你知道這些元素都是正數,並且小於一個數字N.在數組中找到總和的算法?
有人可以給我一個算法的一般高級描述,以確定是否有一個子集所有元素都加到N的數組?
它不需要特別有效;我正在使用的集合非常小。
假設你有一些元素,你知道這些元素都是正數,並且小於一個數字N.在數組中找到總和的算法?
有人可以給我一個算法的一般高級描述,以確定是否有一個子集所有元素都加到N的數組?
它不需要特別有效;我正在使用的集合非常小。
如果效率不重要,在一個高層次的算法是:
input: array A[1..K] of positive numbers, positive N
for each subset S of { 1..K }
sum = 0
for each i in S
sum = sum + A[i]
end
if (sum equals N) return true
end
return false
僞代碼。非常低效。
if empty(numbers) return false
return hasSumSubset(numbers, N)
boolean hasSumSubset(numbers[], N):
p = pop(numbers)
if empty(numbers) return N == p
return hasSumSubset(numbers, N-p) or hasSumSubset(numbers, N)
如果你真的實現這個確保numbers
被複制(不是由參傳遞)的遞歸調用;否則它將無法正常工作。