題目

　　給定一個正數數組arr，其中所有的值都是整數，以下是最小不可組成和的概念：把arr每個子集內的所有元素加起來會出現很多值，其中最小的記為min，最大的記為max。在區間[min, max]上，如果有數不可以被arr某一個子集相加得到，那么其中最小的那個數就是arr的最小不可組成和。在區間[min, max]上，如果所有的數都可以被arr的某一個子集相加得到，那么max + 1是arr的最小不可組成和。

進階題目

　　如果已知正數數組arr中肯定有1這個數，是否能更快地得到最小不可組成和

原問題：使用動態規劃。arr中所有數的相加和sum即是該數組的最大累加和，所有arr子集的累加和必然在[0, sum]區間上。生成長度為sum+1的dp數組，dp[i] == True表示i這個累加和可以被arr的子集相加得到，否則不能。如果arr[0…i]這個范圍上的數組成的子集可以累加出k，那么arr[0…i+1]這個范圍上的數組成的子集中必然可以累加出k + arr[i+1]。時間復雜度O(N*sum)，空間復雜度O(sum)

def unformedSum1(arr):import sysif arr == None or len(arr) == 0:return 1sumMax = 0sumMin = sys.maxsizefor i in range(len(arr)):sumMin = min(sumMin,arr[i])sumMax += arr[i]dp = [False for i in range(sumMax+1)]dp[0] = Truefor i in range(len(arr)):for j in range(sumMax,arr[i]-1,-1):if dp[j-arr[i]]:dp[j] = Truefor i in range(sumMin,len(dp)):if not dp[i]:return ireturn sumMax + 1

進階問題：具體過程如下：將arr進行排序，排序后必然有arr[0] == 1。從左往右計算每個位置i的range。range表示當計算到位置arr[i]時，[1, range]上所有的數都可以被arr[0…i-1]的某一個子集累加出來。初始時range = 0。如果arr[i] > range+1。說明在arr[0…i]上，range+1這個數一定不能累加出來。此時返回range + 1即可。如果arr[i]≤range+1arr[i]≤range+1，說明[1,range+arr[i]]區間上所有的正數都可以被arr[0…i]上的某一個子集累加出來，所以令range += arr[i]，然后繼續計算下一個位置。時間復雜度O(NlogN)，空間復雜度O(1)。

def unformedSum2(arr): if arr == None or len(arr) == 0:return 1arr.sort()range_ = 0for i in range(len(arr)):if arr[i] <= range_ + 1:range_ += 1else:breakreturn range_+1

?

總結

以上是生活随笔為你收集整理的正数数组的最小不可组成和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。