修改子集合

給定N個正整數的數組。設最小元素爲L，所有元素的總和爲S.修改子集合

我需要找出是否對於每個整數X（其中X介於L和S之間）可以選擇數組的子集該元件的該子集中的總和等於X.

例：

讓N=5和陣列是{4,8,2,1,16}。那麼這裏所有的元素都可以在1到31之間，所以這裏的答案是「是」。

如果假設N=4和數組是{5,1,2,7}。然後，對於1到15之間的值，不能進行值4和11。 所以這裏回答是「不」。

來源

2014-01-25 user3219308

你需要提供你所嘗試過的。 – herohuyongtao

@harold No. {1,2,3}是一個反例。 – amit

@herohuyongtao我知道找不到這個數組返回的最小數字，但是不知道如何解決這個問題 – user3219308

我知道發現不能用這個數組返回的最小數目，但不知道如何解決這個問題

第一，請問該數組只有一個元素？如果是這樣，答案是肯定的。

否則，找到最小不可能的總和。它比S大嗎？如果是這樣，答案是肯定的。否則，答案是否定的。（如果最小值小於L，則數組不包含1，並且S-1是不可能的總和。）

要查找最低不可能的總和，我們對輸入進行排序，然後找到最低不可能的總和數組的每個前綴。在Python：通過感應

def lowest_impossible_sum(nums): 
    nums = sorted(nums) 
    partial_sum = 0 
    for num in nums: 
     if num > partial_sum + 1: 
      return partial_sum + 1 
     partial_sum += num 
    return partial_sum + 1

證明正確性：

設A是排序後的數組。如果A[0] > 1，那麼1是不可能的最低總和。否則，A[:1]的元素可以產生高達sum(A[:1])的所有總和。

假設歸納法，可以選擇A[:k]的子集來產生所有總和爲sum(A[:k])的總和。

如果A[k] > sum(A[:k]) + 1，那麼sum(A[:k]) + 1是不可能的最低總和;它不能由A[:k]的子集生成，並且添加不在A[:k]中的元素將無濟於事，因爲它們都太大。
如果A[k] <= sum(A[:k]) + 1，那麼A[:k+1]的子集可以產生高達sum(A[:k+1])的每個和。達到sum(A[:k])的每個總和已經可以通過歸納假設產生，並且從sum(A[:k]) + 1到sum(A[:k+1])的總和可以通過選擇A[k]和合適的子集A[:k]加起來得到。

設x是第一個索引，例如A[x] > sum(A[:x]) + 1或len(A)如果沒有這樣的索引。通過歸納，每個總計可達sum(A[:x])。但是，無論是因爲x超過了數組的尾數還是因爲A[x] > sum(A[:x]) + 1，都無法產生總和sum(A[:x]) + 1。因此，我們只需要搜索x並返回sum(A[:x]) + 1。這就是算法的作用。

來源

2014-01-25 09:42:53 user2357112

可否請您提供一個有效的算法，因爲根據我的算法，我將檢查從一個開始的每個數字，對於大型的N – user3219308

@ user3219308來說效率太低：那麼，找到最低不可能總和的算法相當低效。我將用一種應該能夠快速解決這兩個問題的算法進行編輯。 – user2357112

還有一個問題，最小數目可能小於L.但是，我99.9％相信，如果1不在數組中，並且數組包含多於1個元素 - 則無法獲得全部總和。（這個聲明需要證明！）。然而，這個解決方案在arr = [5]中失敗了，例如，無法實現的最小元素是1，答案仍然是'是'。 – amit

首先對數組中的所有元素進行排序。如果你想從數組的元素中得到L和S之間的所有值，那麼L = 1並且元素應該是2^i的形式。最大的元素可能不是形式2^i，因爲總和不必是形式（2^i - 1）。

來源

2014-01-25 09:45:44

查看阿米特的反例。 – user2357112

@ user2357112：謝謝指出。現在我糾正了算法。最偉大的元素可能不是形式2^i。 –

仍然錯誤。「{1,1,1}」是我認爲你想說的一個反例。 – user2357112

回答

相關問題