Проблема заключается в том:найти подмножество, которое суммирует до к, используя черный ящик в O (п)
Предположим, что вам дается алгоритм как черный ящик - вы не можете увидеть, как она предназначена - это имеет следующие свойства: если вы вводите какую-либо последовательность действительных чисел и целое число k, алгоритм ответит ДА или НЕТ, указывая, есть ли подмножество чисел, сумма которых равна точно k. Покажите, как использовать этот черный ящик, чтобы найти подмножество заданного набора чисел S, сумма которого равна k. Вы можете использовать черный ящик O (n) раз.
Перед тем, как опубликовать этот вопрос, я уже искал точно такой же вопрос:
An algorithm to determine a subset sequence in O(n)?
Using subset-sum oracle to determine which numbers are members of the subset
Я не могу найти удовлетворительного ответа на эти должности. Пусть
S = {1, 2, 3, 4, 5, 6, 7, 8}, к = 7
querrying Oracle (S или S \ setminus любой elemnt), будет возвращать ДА. что не помогает подойти к определенному подмножеству, суммирующему до k.
Итак, есть три повторяющиеся темы, и все, что вы пробовали, передает всю сумму только? Абсолютно никакой другой идеи не приходит в голову? – Groo
Какая часть первой ссылки не поможет? Также обратите внимание, что могут быть несколько подмножеств, которые суммируются до k, и неважно, какой из них вы найдете. – Keiwan
Я объяснил, почему я думаю, что это не полезно. Это мое последнее предложение. допустим, я делаю 8 запросов: Oractle (S \ setminus 1 element), получив 8 YES. который говорит мне, что каждый элемент S не должен находиться в подмножестве, которое суммируется с k. это не помогает. – Jamesszm