使用子集和oracle来确定哪些数字是子集的成员 [英] Using subset-sum oracle to determine which numbers are members of the subset

问题描述

我在解决这个特殊的作业问题时遇到了麻烦。问题出在这里：

I am having trouble starting off this particular homework problem. Here is the problem:

假设给定一个算法作为黑盒–您看不到它的设计方式–它具有以下属性：如果输入实数和整数k的序列，该算法将回答YES或NO，指示是否存在一个总和为k的数字子集。演示如何使用该黑盒查找给定序列X1….. Xn的总和为k的子集。您可以使用黑盒O（n）次。

Suppose that you are given an algorithm as a black box – you cannot see how it is designed – it has the following properties: if you input any sequence of real numbers and an integer k, the algorithm will answer YES or NO indicating whether there is a subset of numbers whose sum is exactly k. Show how to use this black box to find the subset of a given sequence X1, …., Xn whose sum is k. You can use the black box O(n) times.

我认为应该首先对序列进行排序，并且所有<仅应考虑k。任何帮助入门将不胜感激。谢谢。

I figure that the sequence should be sorted first, and anything < k should only be considered. Any help to get started would be greatly appreciated. Thanks.

推荐答案

排序是错误的方法。这样考虑：如何使用oracle来确定集合中的某个特定项目是否是总和的一部分？一旦知道该项目是否为总和的一部分，如何使用oracle判断其他项目是否为总和的一部分？

Sorting is the wrong approach. Think about it this way: how can you use the oracle to determine whether a particular item in the set is part of the sum? Once you know whether that item is part of the sum, how can you use the oracle to figure out whether some other item is part of the sum?

这篇关于使用子集和oracle来确定哪些数字是子集的成员的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！