algorithm - 使用子集和 oracle 确定哪些数字是子集的成员

Question

我在开始这个特殊的家庭作业问题时遇到了麻烦。这是问题所在：

假设给你一个算法作为一个黑盒子——你看不到它是如何设计的——它具有以下属性：如果你输入任何实数序列和一个整数 k，算法将回答 YES 或 NO 指示是否存在总和恰好为 k 的数字子集。展示如何使用这个黑盒来找到给定序列 X1, ...., Xn 的子集，其和为 k。您可以使用黑盒 O(n) 次。

我认为应该首先对序列进行排序，并且应该只考虑 < k 的任何内容。任何帮助开始将不胜感激。谢谢。

score 1 · Accepted Answer

排序是错误的方法。这样想：你如何使用预言机来确定集合中的特定项目是否是总和的一部分？一旦您知道该项目是否是总和的一部分，您如何使用预言机来确定其他项目是否是总和的一部分？

score -1 · Accepted Answer

黑盒是这样的，在 C# 中（忽略我使用 int 而不是 real 作为序列，这对问题无关紧要）。

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

您的任务是传入序列的子集并找出序列的哪一部分等于k。

从整个序列开始，看看是否k在其中。然后，如果它包含k，则尝试一个子序列来查看该子序列是否包含k。重复直到你有包含的子序列k。

2 回答 2