Выбор подмножеств набора так, чтобы подмножества удовлетворяли глобальному ограничению

Question

У нас есть набор элементов I = {i_1, i_2, ..., i_n}. Каждый из этих элементов имеет то, что мы называем значением p , которое является некоторым действительным числом. Мы хотим выбрать подмножество I, назовите его I ', размера m (для некоторых m с 1 <= m <= n), чтобы среднее значение <em>p значений элементов в I' попадает в некоторый указанный диапазон, [p_l, p_u]. (Например, нам может потребоваться среднее значение p между 0,70 и 0,74.) Более того, мы хотим сделать это эффективно.

Мы надеемся сделать это за O (n) время, но любой алгоритм за полиномиальное время достаточно хорош. Мы, конечно, не хотим просто пробовать каждое возможное подмножество I размера m, а затем проверять, удовлетворяет ли оно усредненному ограничению p-значения.

Наконец, мы будем делать это неоднократно, и мы хотим, чтобы выбранные подмножества были равномерно случайным распределением по всем возможным таким подмножествам.

Есть ли способ сделать это?

Answer 1

Если у вас есть подмножество и его сумма, если вы масштабируете сумму на | подмножество + 1 | / | подмножество |, каждый новый добавляемый вами элемент вносит линейный вклад в сумму.Таким образом, это кажется очень похожим на проблему суммы подмножеств (NP-полная), где цель состоит в том, чтобы найти все подмножество, сумма которых равна 0, хотя здесь мы хотим, чтобы сумма была близка к 0. Например, если у вас большоеустановить, где один элемент находится примерно в приемлемом p-диапазоне, если вы сделаете схематичное предположение, что этот элемент не имеет значения, вдруг он практически эквивалентен ... при условии, что у вас есть большое количество положительных и отрицательных p-значений, ипроблема не построена противником.Если это так, вы можете использовать одно из двух аппроксимирующих решений, заданных в http://en.wikipedia.org/wiki/Subset_sum_problem, сделать равенство «нечетким» и просто добавить «зарезервированный» элемент с 0,7.