数学建模社区-数学中国

标题: 如何证明一个问题是NP难。 [打印本页]

作者: winning3 时间: 2009-7-7 16:17
标题: 如何证明一个问题是NP难。
1．
某旅馆有一间会议厅，顾客可以预先预定使用该会议厅的天数。证明：若至少有一人要求使用该会议厅的时间是确定的，且分配给预定者使用该会议厅的时间期限是有上界的（即只制定规定天数的使用计划），则管理员要确定是否可以不拒绝顾客的问题是NP难的（解：设有n个顾客各预订了a1,…,an天，∑ai = 2B ，D = 2B +1, 另有一人预定在t = B 时使用1天，确定是否要拒绝顾客等价于划分问题）

作者: u2002040838 时间: 2009-7-8 22:57
不懂新手

作者: Kadyniost 时间: 2009-8-10 00:22
。。。。。。。。。

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)