問題陳述如下：鑑於N。我們需要找到x1,x2,..,xp，使得N = x1 + x2 + .. + xp，p必須是最小值（意味着總和中的項的數量），並且我們還必須能夠從總和中獲得從1到（N-1）的所有數字（x1，x2，x3 ... xp）的子集中，並且集合中的數字也可以重複。算法獲得與最小數量的條款

例如，如果N = 7。

7 = 1+2+4 而6= (2,4)，5= (4,1)，4 = (4)，3=(1,2)等。

實施例2： 8 = 1+2+4+1

實施例3：（無效） 8 = 1 + 2 + 5 但是，我們不能從（1,2,5）。所以子集得到4（1 ，2,5）不是有效的組合

我的方法是，如果'N-1'可以寫成p項的總和而'N'或者有p或p + 1項。但是這種方法將需要檢查總和爲「N-1」並具有「p」項的所有可能的組合。除此之外，任何人都可以有更好的解

解決方案：

第一步：假設我們有我們的一套作爲我們的答案「K」的條目。因此，我們可以從這些數字中獲得2^K個不同數量的總和，因爲每個條目都會出現或不出現在總和中。而且如果數字是「N」，我們需要計算'1'到'N'的和。因此

（2^K -1）= N

K =日誌（N + 1）

第二步：

的第一步後，我們知道，我們的回答必須包括「K」的項，但這些有什麼實際的條目是？假設我們的條目是（a1，a2，a3 ... ak）。所以編號P可以寫爲 P = a1 * b1 + a2 * b2 + a3 * b3 .... + ak * bk。在這裏，我們可以看到P是二進制數的一個十進制表示（b1 b2 b3 bk），因此我們可以取一個[i] = 2 ^（i-1）。

來源

2013-07-13 Manish

如上所述，您的算法對於大多數數字不可行。例如，對於數字8，不可能構建一組*獨特的*數字，使得它們加起來爲8，並且可以合併以使每個數字從1到8.事實上，只有少於一個的數字是可能的比二的力量。 – llb

我們可以寫8爲1 + 2 + 4 + 1。對？ – Manish

@Manish - 如果你被允許重複條件，那麼問題就會減少到列表x1 = 1。顯然，我們可以產生任何數字，可以重複添加1 ... –

您應該取所有數字1,2,4 .... 2^k，N-（1 + ... + 2^k）。（最後一個唯一的，如果它不等於0）

證明

首先，如果我們只拿到k數字，我們可以得到最大2^k - 1不同的資金，除了0。所以，如果N>=2^k ，我們至少需要k + 1號碼。所以你可以看到，如果我們的數字組糾正它的最小按大小（或最小值之一）
可以很容易地看到，我們可以從0使用第一數字得到任何數量2^(k+1) - 1。如果我們需要更多？我們只是得到最後一個號碼，因爲它小於2^(k + 1)。並使用第一個元素獲得差異

來源

2013-07-13 02:28:15 RiaD

非常好..而且我從過去的一天開始思考這個問題..：O – Manish

難道有人會說這個證明很難理解嗎？（我確實這麼認爲）我會試着重寫它。 – RiaD

我不明白的證明，但這只是因爲我不明白擺在首位 – aaronman

我還沒有把這個數字用完，但是你應該非常感興趣的是你列出了兩個前三個冪。

如果我正在尋找更好的解決方案，那就是我要開始的地方。

來源

2013-07-13 02:10:38

這不是一個答案，如果我正確理解問題，他只列出2的前3個冪，因爲那是他的名單，不是因爲它有什麼特別之處 – aaronman

不，我同意，我沒有給他用紫色弓包裹的答案。以爲他可能喜歡搞清楚 - 這暗示應該讓他在那裏。 –

嗯，那就不要張貼答案，把評論 – aaronman

算法獲得與最小數量的條款

回答

證明

相關問題