又见背包问题

lonerwolf

21个石头，ABAB的拿，一次拿1-4个，不能不拿，最后一个拿的输。。。编程要B赢

这是背包问题么？又是什么类型的背包？。。。。

asha_hi

不算背包。这种题很简单，不管是抢还是让，都可以转化成抢的问题。
抢n：n%(k+1)，得之者胜
让n：(n-1)%(k+1)，得之者胜

lonerwolf

回复 2# asha_hi

{:3_183:}
   完全不懂，看来算法完全不太行

daybreakcx

每次不管A取的个数k是多少（1-4）之间，B都取5-k个，这样每次都少5个，最后21=4*5+1会剩下一个，必然是留给A的
这里可以考虑到一般情况，如果每次最多取k个，原来有n个石子，只要n%(k+1)=1则后手（原来的B）有必胜策略，否则先手可以先将局势变成后手必胜策略然后让先手后取胜（比如原来有22个，22%5=2,A可以先拿走1个，这时候轮到B了，A获胜）。

lonerwolf

回复 4# daybreakcx


   明白了，此时的心情犹如您的头像