3

好的，所以我尝试对项目的向量使用排序，所以两个相邻项目的大小是 <= 2d。所以这是我的尝试：

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);

我做错了什么，或者甚至不可能使用这样的条件进行排序？

4

3 回答 3

5

甚至不可能使用这样的条件进行排序？

不，比较器sort必须满足严格的弱排序标准，而你的显然不满足（例如它不是反身的）。

于 2011-02-27T19:08:17.780 回答
2

这个问题不能在 O(N log N) 时间内解决。我不知道它是否是 NP 难的，但它非常重要。我确实认为可以肯定地说，解决代码中表达的问题的程序需要指数级的时间。有这样的程序：我认为它可以被摆弄并插入线性优化器。

没有标准的库函数能让你获得一个通用的解决方案。没有比 O(N log N) 慢的标准库函数，也没有一个能解决可能难以解决的问题。

例如，如果每个sizeequals ，这个问题就很难解决10 * d。

于 2011-02-27T19:18:10.377 回答
0

您使用的 sort() 方法错误。

STL 排序用于对元素列表进行排序。对于“订购”，您需要满足以下条件：

  1. 如果 check( A, B ) == false AND A != B，则 check( B, A ) 返回 true。
  2. 如果 check( A, B ) == false AND check( B, C) == false AND A, B, C 不同，则 check ( A, C ) 返回 false。

考虑到您的项目列表 S 和您希望项目所在的顺序，您可以在哪里使用 STL 的 sort() 的一个好主意：

  1. 如果 S 中项目的顺序发生变化，则输出顺序应保持不变。
  2. 输出是独一无二的。
  3. 输出顺序中的所有项目都具有某种关系，即严格的偏序关系。

如果是这种情况，那么您可能可以编写检查功能来为您工作:)

于 2011-02-27T19:10:07.390 回答