計算數學 Problem Solving- Knapsack problem

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