我有一個任務：數字陣列 [8 1 2 8 2 10 4 5]，需要確定它的任何元素是否可以是其總和的一半。在示例中，元素之和為 40，一半和為 20。元素可以是 8,2,10 或 5,1,4,10 。不管數字是什么，只有真偽結果。我通過遞回檢查所有可能的數字總和，我很困惑如何將其轉換為回圈
private static boolean isExist(int[] data, int n, int sum) {
if (sum == 0)
return true;
if (n <= 0)
return false;
if (data[n - 1] == sum)
return true;
if (sum < data[n - 1])
return isExist(data, n - 1, sum);
return isExist(data, n - 1, sum - data[n - 1]) || isExist(data, n - 1, sum);
}
uj5u.com熱心網友回復：
A[]制作長度陣列sum 1，制作A[0]=1
對于 value 的每個元素e：反向檢查（從陣列末尾到開頭）if A[i-e]==1，在本例中為 make A[i]=1。（這表示 sumi可能由當前元素和先前檢查的元素組成）
如果A[sum]變為 1，則需要的子集確實存在。
Python中的作業示例來演示：
L = [7, 9, 3, 4, 6, 7]
S = sum(L) // 2
A = [0]*(S 1)
A[0] = 1
for e in L:
for i in range(S, e-1, -1): // scan backward
if A[i-e]:
A[i] = 1
print(A, A[-1] > 0)
>> [1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] True
L = [7, 9, 3, 4, 6, 13]
>> [1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0] False
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/514870.html
標籤：爪哇算法递归动态规划
下一篇：如何獲得解決方案背后的直覺？