演算法的Dynamic programming與遊戲中的應用（上）

常常有人會在問：讀資訊工程/計算機科學的大概都在干嘛？是不是會寫程式就好啦？
所以剛好最近又在讀演算法、想說來介紹一下、讓大家認識一下這個科系除了寫程式
以外、我覺得更重要的東西。

當然、學東西就是要好好應用嘛、既然在這個大樓發文、就是要應用在大家有興趣的
地方：因此在下篇中將會介紹Dynamic programming在遊戲攻略時（對玩家而言）的應
用，使用範例是技嘉戯画的Baldr Force的Combo設計、有興趣的人也可以去思考一下對
於設計者而言、如何利用來設計遊戲平衡性。

＊我恨讀書眾可以離席了（爆）

如果你覺得在離開學校以後、偶爾有一點求知的慾望、很高興你還坐的住。讓我們開
始吧。

首先要先介紹一下什麼叫做「演算法」、其實說簡單一點：
就是「設計解決問題方式的方法」。或者你也可以說成是「幫助你思考問題解決方法
」的一門學問。本來而言、這個科目需要有一些關於資料結構的基礎、不過所幸我們
這次介紹的範圍還算是用不太到、我們改用遞迴的方式來思考。

希望這樣的介紹已經讓你精神為之一振、因為你也想要知道遇到一個問題該怎麼開始
著手解決、對吧？

今天的主題叫做Dynamic programming、是拿來解決一些比較「非直覺性」的問題。
為了方便說明、我們用舉例的方式來看看：

今天假設你是一個小偷、你身上只有一個四公升的大鐵桶，來到一間工廠偷東西。
工廠中有以下三種液體（？）皆超過四公升以上可以讓你偷：
1. 水
2. 沙茶醬
2. 石油

基本上只要腦袋正常、而且不考慮重量因素正常人都會想偷石油吧？
（主：我要偷沙茶醬啦、鳥：搞不好沙茶醬比石油重喔﹍﹍）
這種直覺的「哪個貴/好、就盡量拿那種」就稱為Greedy Algorithm（貪婪演算法）
事實上大家都會、也沒啥學問﹍﹍

「等等、我說過了今天主角叫dynamic programming、請稍安勿燥」（接住台下丟上來的
雞蛋）

那現在考慮另一個情況，也一樣是很生活化的例子：

今天樑上君子的你進入一個銀行保險庫，裡面大量的各式貴重金屬、但是你只能帶50公斤
離開
1. 金屬1 重10公斤 60美元 單價值6美元/公斤
2. 金屬2 重20公斤 100美元 單價值5美元/公斤
3. 金屬3 重30公斤 120美元 單價值4美元/公斤
請問這些金屬各一塊、你應該帶哪些走呢？
如果是從單價最高的來看、攜帶金屬1跟金屬2的話、能帶走只有160美金。
但是如果改拿單價看起來最差的金屬2跟金屬3的話、卻能帶走220美金。

這就是dynamic programming派上用場的時候了。不過打到這裡累了點、原訂兩篇的分拆成
三篇好了（炸）、下回分曉：如何思考解決這一類的問題。