第四章若博弈的某个策略组合不是Nash均衡,则每位参与者均可通过单方面改变自身的策略使其费用减少。( )
答案:错
考虑背包问题的在线形式。背包容量事先已知,物品一个个相继出现,物品出现后方知其价值和大小。具体地,第个物品在第个物品是否放入背包已被确定后才出现,且此前已作出的前个物品是否被放入背包的决定不可更改。该在线问题的下界为( )。
答案:
答案:。
;
;。
答案:若存在的竞争比为的在线算法,则问题的下界至多为。
;若是的一个下界,则可能存在竞争比大于的在线算法。
答案:四名同学均不参加活动。;两名同学参加活动。