新春購物大減價引發的數學難題,大家參詳一下~~

要嘗試解決這個問題，本人作了如下分析：
為方便討論，定義C(a1, a2, ..., an)為n件貨品售價的極小值，其中$a1, $a2, ..., $an為各貨品的標價。
首先給出一個推論：
設有兩批各n件的貨品，其標價分別是$x1, $x2, ..., $xn，以及$y1, $y2, ..., $yn。
若對於所有正整數i (i <= n)，恆有xi >= yi，則C(x1, x2, ..., xn) >= C(y1, y2, ..., yn)。
*******************
由上述推論可得：
(1) 在「買一送一」的情況下，要使售價取極小值，該「買一送一」組合中，「較便宜的一件」貨品應定為所有較便宜的貨品中最昂貴的一件。
　　證明：設餘下的貨品標價為$x1, $x2, ..., $xk，其中x1 >= ... >= xk。
　　　　　則C(x2, x3, ..., xk) <= C(x1, ..., xr-1, xr+1, ..., xk)，其中2 <= r <= k。
　　例：設貨品標價為$100、$90、$85、$50。
　　　　則「買一送一」的組合只可能為{$100, $90}、{$90, $85}、{$85, $50}，
　　　　而不會是{$100, $85}（忽略了$90）、{$100, $50}（忽略了$90和$85）或{$90, $50}（忽略了$85）。
(2) 設A為n件貨品中最昂貴的，其標價為$x。則貨品總售價的極小值只有兩種可能性：
　　(i) A取「六折」：則
　　　　　售價 = $0.6x + 餘下的(n-1)件貨品的極小售價；
　　(ii) A與第二昂貴的貨品「買一送一」：則
　　　　　售價 = $x + 餘下的(n-2)件貨品的極小售價。
　　兩者取其極小值，便為n件貨品的極小售價。
(3) 我們可先將貨品按標格排列，然後依序求最便宜的1件、2件、3件、...、(n-2)件、(n-1)件貨品的極小售價，以求出該n件貨品的極小售價。
*******************
根據上述討論，現給出其中一個算法：
首先將n件貨品依標價排序。
故不失一般性，可設$a1, $a2, ..., $an為該n件貨品的標價，其中a1 <= a2 <= ... <= an。
定義
　　m0 = 0，m1 = 0.6a1，及
　　mk = min{0.6ak + mk-1, ak + mk-2}（2 <= k <= n） ...(*)。
則該n件貨品總售價的極小值為$mn。
*******************
試以上述的$100、$90、$85、$50作為例子：
排序：50 <= 85 <= 90 <= 100
m1 = 0.6(50) = 30；　　　 （組合：{50}）
m2 = min{0.6(85) + 30, 85 + 0}
　 = min{81, 85} = 81；　 （極小值取前者，組合：{50}, {85}）
m3 = min{0.6(90) + 81, 90 + 30}
　 = min{135, 120} = 120；（極小值取後者，組合：{50}, {85, 90}）
m4 = min{0.6(100) + 120, 100 + 81}
　 = min{180, 181} = 180；（極小值取前者，組合：{50}, {85, 90}, {100}）
故可知極小售價為$180（$100, $50取六折，{$90, $85}買一送一）。
*******************
最後給出上述算法之複雜度分析：
(1) 利用Quicksort、Mergesort等將{ak}排序，複雜度為O(n lnn)；
(2) 利用遞歸關係(*)求mn的值，複雜度為O(n)。
故綜合而言，上述算法的複雜度為O(n lnn)。

至於這是否一個「好的」方法，小弟學力不足，未敢置喙。 ^^