105 第六題 召喚獸之最大戰鬥力總和

       某電玩遊戲推出比特幣的制度，玩家可以使用自己所擁有的比特幣，來馴服召喚獸，每一種不同的召喚獸分別需要不同數量的比特幣，而且每一種召喚獸所提供的戰鬥力也不同。假設召喚獸們之戰鬥力總和值可以直接將其加總，也可馴服多隻同一物種召喚獸，未使用完的比特幣數可以剩下。
    某玩家希望能夠使用他所擁有的比特幣，馴服各種召喚獸，以便提升自己的戰鬥力總和值到最高，請幫他計算，他的比特幣數究竟能夠獲取的最大戰鬥力總和是多少呢？
    下表中列出了馴服各種召喚獸所需之比特幣數以及每一種召喚獸的戰鬥力，且每一種召喚獸的數量有限。

召喚獸名稱
戰鬥力馴服召喚獸所需比特幣數
A
X (於程式執行時輸入)
30
B
75
18
C
45
8
D
20
5
E
2
1
F
300
50
G
70
16
H
50
10
I
25
4
J
3
1

輸入說明
    輸入第一個正整數 k 代表 "比特幣數"，輸入第二個正整數 x 代表 "召喚獸A之戰鬥力值 X"。
    再依序輸入 10 個正整數 (a1,a2,a3...a10) 分別代表 "召喚獸 A~J 的數量"。
    以上所輸入之每個正整數值均可包含 0。
( 0 ≤ k ≤ 10000，0 ≤ x ≤ 1000，0 ≤ a1,a2,a3...a10 ≤ 100)
輸出說明
    輸出一個正整數代表 "獲得的最大戰鬥力總和"。

範例
輸入
輸出
3,200,1,1,1,1,1,1,1,1,1,1 5
5
45,100,1,3,1,5,1,10,1,50,1,1
228


說明：
104 、105、106 年這三年的第 6 題，都是相同的題目，是背包問題，為 NP 問題，
但因為數字小，所以用動態規劃，甚至暴力法就可解決，104 年曾介紹暴力法，
及動態規劃演算法，在此也要再介紹一次動態規劃，不過這次會加快速度，籌碼是
使用陣列記憶曾經發生過的最大值，這樣若要再計算最大值，就可以直接取用陣列值，
省去運算時間，是一種空間換取時間策略。
此演算法不紀錄最佳狀況下，所訓練的召喚獸是那一類及其數量。

以下程式， Knapsack 是主要遞迴程式，傳入召喚獸種類及比特幣最大數，傳回此條件下
最好的選擇。

演算法
設 p 為召喚獸種類個數(因 p 只是索引招喚獸的陣列註標，所以從 0 開始，w 為可比特幣數量。
1. 若 p<0 (表示沒有招喚獸) 或 w <=0 (表示沒有比特幣可用) 則傳回 0
2. 如果之前已經取得在 p, w 情況之下，最好的召喚獸方式，則傳回當時紀錄在陣列的值。
3. 計算比特幣數量能訓練召喚獸的數量及目前召喚獸的存量，取最小值(設為 ml)。
4. 針對 p 這一類召喚獸，從 0 至 ml 數量開始訓練，訓練後剩下的比特幣再拿去訓練下一類的招喚獸。
5. 合併 p 這類召喚獸訓練出的戰鬥力及下一類召喚獸訓練所得戰鬥力。
6. 比較之前紀錄的最好戰鬥力值，若有比較好，則更新紀錄。
7. 將結果(最好的戰鬥力值) 放到陣列中。
8. 傳回最好的戰鬥力值。