DFS+剪枝

令dfs(int it,int v,int pw)

其中it/v/pw分別代表 目前看到第it個位子/用了v塊錢/總戰力為pw

初始態dfs(0,0,0)，(選手的金額為v，戰力為w)

每一層it對每個選手都做一次dfs   //dfs(it+1,v+player[it][i].v,pw+player[it][i].w);

這裡有個細節，因為可以不選，所以還要再dfs一次  //dfs(it+1,v,pw);

基本上紀錄最大的合法pw就可以不WA了

複雜度:時間O(N^M)//呵呵你沒看錯，所以要剪枝

空間O(N*M)

剪枝一:當v花的比M還多時，不管怎麼跑都不可能是答案，直接return

剪枝二:紀錄最佳解，這需要用到解法二的概念，令DP[5005][N]表示看完N個人的情況下到達戰力pw所花的最少錢，當你目前花的錢超過時就可以return了 //不過空間又變成了O(S*N)

基本上只用上面兩個就能AC了(17ms)

剪枝三:排序選手，對每層的選手按照CP值(戰力/金額)從大到小排序，DFS的樹會小一點，因為後面比較差的選手會被剪枝二給減掉