10465: Homer Simpson ★★★☆☆ 題組：Problem Set Archive with Online Judge 解題者：黃榆涵 解題日期：2013年5月9日 題意：Homer Simpson 吃A漢堡要花m分鐘，吃B漢堡要花n分鐘，t分鐘內(0<m,n,t<10000)在盡可能不浪費時間的前提下，盡可能的吃最多的漢堡。
解法：Unbounded Knapsack Problem (重量->時間， 題意範例： 3 5 54 18 (A漢堡吃18個) 3 5 55 17 (A漢堡吃15個，B漢堡吃2個) 7 8 27 3 3 (B漢堡吃3個，剩3分鐘 ) 解法：Unbounded Knapsack Problem (重量->時間， 價值->漢堡數) 搭配Dynamic Programming。 對一個漢堡來說，我們可以選擇吃或不吃。 假設吃一個漢堡需n分鐘，當時間為i 分鐘時， 則最多可吃到的漢堡數量為 sum[i] = max( sum[i] , sum[i-n]+1) ^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^ 不吃 吃
第4分鐘時，最佳狀態可以吃1個A漢堡但剩餘有剩餘時間， 所以設為-1 第5分鐘時，最佳狀態可以吃1個B漢堡 解法範例： 3 5 10 2 第3分鐘時，最佳狀態可吃1個A漢堡 第4分鐘時，最佳狀態可以吃1個A漢堡但剩餘有剩餘時間， 所以設為-1 第5分鐘時，最佳狀態可以吃1個B漢堡 第6分鐘時，最佳狀態可以吃2個A漢堡 ….. 第8分鐘時，最佳狀態可以吃1個A漢堡，1個B漢堡 第10分鐘時，最佳狀態可以吃2個B漢堡，且沒有剩餘時間 分鐘數 1 2 3 4 5 6 7 8 9 10 A -1 B
討論：時間複雜度為O(t) ，t為時間。