<algorithm> сортировать пользовательские условия - PullRequest
Новая
       8

<algorithm> сортировать пользовательские условия

3 голосов
/ 27 февраля 2011

Хорошо, я попытался использовать сортировку по вектору элементов, чтобы размер двух вспомогательных элементов был <= 2d. Итак, вот моя попытка: </p> 

struct item{
    long number;
    long size;
};

// d is global variable.
bool check(const item& x, const item& y)
{
    return ((x.size + y.size) <= (2 * d));
}

// Items is a vector of item.
sort(items.begin(), items.end(), check);

Что я делаю не так или даже невозможно сортировать, используя такие условия?

Ответы [ 3 ]

5 голосов
/ 27 февраля 2011

невозможно даже отсортировать, используя такие условия?

Нет. Компаратор в sort должен удовлетворять критериям строгого слабого порядка , который, по вашему мнению, не соответствует (например, он не является нерефлексивным).

2 голосов
/ 27 февраля 2011

Эта проблема не может быть решена за O (N log N).Я не знаю, если это NP-жесткий, но это довольно нетривиально.Я думаю, что можно с уверенностью сказать, что программа, решающая проблему, как указано в вашем коде, потребует экспоненциального времени.Есть такие программы: я думаю, что это можно было бы обойти и подключить к линейному оптимизатору.

Никакая стандартная библиотечная функция не даст вам даже большую часть пути к общему решению.Нет стандартных библиотечных функций более медленных, чем O (N log N), и ни одна не решает проблемы, которые могут быть трудноразрешимыми.

Эта проблема неразрешима, если, например, каждый size равен 10 * d.

0 голосов
/ 27 февраля 2011

Вы используете неправильный метод sort ().

Сортировка STL используется для упорядочивания списка элементов.Для «заказа» необходимо выполнить условия, такие как:

  1. , если check (A, B) == false AND A! = B, то check (B, A) возвращает true.
  2. если check (A, B) == false И check (B, C) == false И A, B, C различны, тогда check (A, C) возвращает false.

Хорошая идея для того, где вы можете использовать STL sort (), учитывая ваш список элементов S и порядок, в котором вы хотите, чтобы элементы были в:

  1. Если порядок элементов в Sизменяется, порядок вывода должен оставаться прежним.
  2. Выход является уникальным.
  3. Все элементы в порядке вывода имеют некоторое отношение, которое является строгим частичным порядком ..

Если это так, то вы, вероятно, можете написать функцию проверки, которая будет работать для вас:)

...