題目連結：
題目大意：
輸入第一列給定兩正整數 T 、 N （T ≦ 10 ^ 5 ， N ≦ 10 ^ 4），代表有 T 小時可以打工且有 N 個工作。接著有 N 列輸入，每列給定一個字串 S 以及兩正整數 M 、 H （S 不含空白字元， M 、 H ≦ 2 × 10 ^ 5），代表每個工作的內容、要花費 H 小時並賺得 M 元。
試問在時間狀況允許下可以賺多少元（假設工作與工作之間的切換不花時間）？且這 N 個工作中，哪個工作的時薪最高？
範例輸入：
範例輸入 #1
10 3
印製鯊魚T恤 20 5
用下巴清潔紅土 20 4
賣蘇菜湯 38 10
範例輸入 #2
20 3
表演喝下可樂混威士忌後嘔吐 10 20
擔任某高一女孩的男友 10000 22
過來阿姨這邊 500 1
範例輸出：
範例輸出 #1
40
用下巴清潔紅土
範例輸出 #2
500
過來阿姨這邊
解題思維：
將 T 視為背包的最大負重量，且將每個工作的 M 視為物品價值、 H 視為物品重量。則本題即變成了典型的背包問題，參見此題。
至於最大時薪就如同其他取最大值的問題而已。對於每個工作 J 與先前時薪最大的工作 MAX 時，其比較式是
J.M ÷ J.H > MAX.M ÷ MAX.H
當上式成立時，也就是工作 J 時薪比先前的最大還要大，所以將 MAX 更新為 J。
但是因為可能會有浮點數誤差，所以我們將上式調整為
J.M × MAX.H > MAX.M × J.H
而因為每個工作的 M 、 H 值皆為正整數，所以不影響原式的真值。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
