В поисках эффективного алгоритма (не Trivial) [закрыто]

Этот вопрос вряд ли поможет любым будущим посетителям; Он имеет отношение только к небольшому географическому району, конкретному моменту во времени или необычайно узкой ситуации, которая обычно не применима к всемирной аудитории Интернета. Для того, чтобы помочь сделать этот вопрос более широко применимым, посетить справочный центр .

закрыто 8 лет назад .

Проблема «Спецификация»:

Это Рождество! Вы должны купить подарки!

У вас есть множество уже существующих пучков игрушек, а соответствующая цена расслоения:

1 0 0 1 0 1 1 1 0 => 58
0 1 0 0 1 1 1 0 0 => 27
1 1 1 0 0 0 1 0 0 => 46
0 0 0 0 1 1 1 1 0 => 73
...

, где 1 указывает, что игрушка находится в комплекте, а 0 Что это не так.

Сейчас находятся промо «Санта-Клаус», а оставшийся пакет X предлагается вам при «специальной цене Promo». Мы скажем x x - это плохое значение , если существует еще один пакет y , так что:

редактировать: чтобы облегчить, я бросил условие 3, но Измененное условие 1 от «подмножества» в «строгое подмножество»

x - это строгий подмножество y
x , дороже y

Цель состоит в том, чтобы реализовать функцию BOOL ISBADSUBSET (X) , который эффективно узнает, является ли x хорошо или нет.

Учитывая, что существуют миллионы связки, сравнивая его с каждым, очевидно, не осуществимым. Более того, вы можете принять предположение, что в существующей коллекции пучков подмножество игрушек всегда дешевле, чем сумерее.

Советы:

Сравнение того, является ли набор представляет собой подмножество или нет другого набора, просто
, можно ограничить сравнения, которые являются оба , содержащие как минимум n и дешевле . Тем не менее, список все еще может быть большим.
Что-то в направлении сита было бы хорошо
, вам не нужно знать , который Bundle лучше ... просто существует тот, который лучше

Можно ли достичь этого в постоянном времени? (Независимо от количества связки в настоящее время в коллекции) ... или хотя бы в журнале (n)?

algorithm data-structures

задан dagnelies 12 September 2011 в 20:57

0 ответов

Другие вопросы по тегам:

algorithm data-structures

В поисках эффективного алгоритма (не Trivial) [закрыто]

0 ответов

Похожие вопросы: