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

不懂新手:dizzy:

Kadyniost 发表于 2009-8-10 00:22

。。。。。。。。。
页: [1]
查看完整版本: 如何证明一个问题是NP难。