[問題] Knapsack problem已刪文
看板Prob_Solve (計算數學 Problem Solving)作者cloud2000s時間5年前 (2019/11/09 17:43)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/1
Time Limit: 2 s
Mem Limit: 65536 KB
Sameple Input 1
9 4
6 8
0 13
14 14
14 1
14 4
13 5
3 11
5 6
3 12
Sample Output 1
994
Sample Input 2
6 6
10 7
0 8
5 3
10 7
2 9
1 3
Sample Output 2
673
我的想法是先用每隻pokemon的b/a值進行sort
然後填dp表格，每一格會存到目前為止的累積攻擊力以及累積經驗值
dp[i][j] = {max(dp[i-1][j-1]累積經驗值E乘上這隻pokemon的atk值+
dp[i-1][j-1]的累積攻擊力,dp[i-1][j]的累積攻擊力)}
比較的順序是優先挑選累積攻擊力較大者
若累積攻擊力相同則挑選累積經驗值較大者
這是我的code
https://paste.ofcode.org/AtMsj5TWpVDTbzz2prSGkp
目前兩個Sample答案都是正確的
但是上傳之後某些情況之下會是Wrong Answer
想問一下我是什麼情況沒有考慮到，應該怎麼修正?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.209.235 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1573292603.A.C77.html
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
