使用subset-sum oracle確定哪些數字是子集的成員

-1

我在開始解決這個特定的作業問題時遇到了問題。這裏是問題：使用subset-sum oracle確定哪些數字是子集的成員

假設你給一個算法作爲一個黑盒 - 你看不到它是如何設計的 - 它有以下屬性：如果你輸入任何實數序列和一個整數k，算法將回答YES或NO，表示是否有一個數字的子集，其總和正好是k。演示如何使用這個黑盒子來找出給定序列X1，...，Xn的子集，其和爲k。您可以使用黑盒子O（n）次。

我認爲序列應該先排序，任何東西只應該被考慮。任何幫助開始將不勝感激。謝謝。

來源

2013-07-10 stochasticcrap

糟糕，這不是子集總和，它使用它。將解決您的問題標題。 –

你不能排序，因爲它會扭曲序列（例如，'4，-2,1,1,0'）在前三個數字中具有總和3，但是'-2,0,1,1,4'根本不包含3個。 – Tawnos

@Tawnos：Sub * set *，不是sub * sequence *。排序不會改變任何東西。（嗯？沒有字面斜體？） – user2357112

排序是錯誤的方法。這樣想一想：如何使用oracle來確定集合中的某個特定項目是否是總和的一部分？一旦你知道這個項目是否是總和的一部分，你如何使用oracle來判斷其他項目是否是總和的一部分？

來源

2013-07-10 01:14:14 user2357112

-1

黑盒是這樣的，在C＃中（忽略我使用int而不是真正的序列，這對問題是無關緊要的）。

bool blackbox(List<int> subSequence, int k) 
{ 
    // unknown 
}

你的任務是通過在序列的子集，並找到什麼流程的一部分等於k。

從整個序列開始，只是爲了看看是否存在k。然後，如果它包含k，請嘗試子序列以查看該子序列是否包含k。重複，直到你有包含k的子序列。

來源

2013-07-10 01:14:24 Tawnos

'user11235813'，因爲我假設你低估了我的答案，你可以（或者誰做過）評論爲什麼？對於可以用O（n）嘗試解決的情況，答案是正確的。如果這確實是一個問題，那麼序列中的任何一組數字都可以被使用，那麼你將有比O（n）更多的嘗試來找到它。例如。如果有五個數字，並且您需要1,3和5，則必須嘗試初始全集，然後嘗試對該集合進行各種排列以找到該集合。 – Tawnos

這就是我。我低估了你的意思，因爲你的答案是以子序列而不是集合的形式出現的，因爲如果問題*是關於序列的問題，那麼這會給解決問題提問者的作業帶來太多的問題。此外，您的評論清楚地表明您沒有意識到問題的子集版本的O（n）解決方案。它確實存在。 – user2357112

我想到的任何答案都有相反的例子，但我可能會誤解這個問題。我的意思是，可以一次去掉一個元素，然後檢查子元素是否還有總和（讀取並移動到下一個有必要的部分），直到觸及每個元素，但是使用問題，它看起來像它想要找到「子集」，而不是「子集」。通常在uni中，這樣的問題需要最小子集。當然，這個問題已經非常措辭，所以不應該太令人吃驚。 – Tawnos

使用subset-sum oracle確定哪些數字是子集的成員

回答

相關問題