[Think] 向量組合問題

以下是我自己設計的一道題目。

今有兩個式子。
式子一：
a1*x1 + a2*x2 + a3*x3 + ...... am*xm
式子二：
b1*y1 + b2*y2 + b3*y3 + ...... bn*yn

其中 a1 ~ am 為常數且 a1 > a2 > ... > am，
且 b1 ~ bn 為常數且 b1 > b2 > ... > bn。

令 x1~xm 以及 y1~yn 皆為任意常數，

我們可以找到 p1~pm 以及 q1~qn 使得以下式子成立：

a1*(x1-p1) + a2*(x2-p2) + a3*(x3-p3) + ...... am*(xm-pm) =
b1*(y1-q1) + b2*(y2-q2) + b3*(y3-q3) + ...... bn*(yn-qn)

求 (p1+p2+p3+...+pm) + (q1+q2+q3+...+qn) 最小值？


[solution]
以下是我的想法。如有錯誤請指正。

1. 假如等號左右兩邊沒有 p1~pm，也沒有 q1~qn，這樣的 Left Hand Side(LHS) 為：a1*x1 + a2*x2 + a3*x3 + ... + am*xm，Right Hand Side(RHS) 為：b1*y1 + b2*y2 + b3*y3 + ... + bn*yn，LHS 和 RHS 先比較大小。
2. 我們將 RHS 和 LHS 想像成槓桿左右力矩平衡的問題。a1～am 以及 b1～bn 視為力臂，x1~xm 以及 y1~yn 視為各個力臂位置的重量。今槓桿左右力矩不平衡，想抽掉重量，總共抽掉的重量要越少越好。
3. 假設上述條件下，LHS 較小，就令 p1~pm 皆為 0。這是很明顯的，p1~pm 要為 0 才會是最佳解。否則 RHS 勢必要抽掉更多重量才能達到力矩平衡。
4. 令 RHS-LHS = k。
5. 找到 bc，使得 (b1*y1 + ... + bc*yc) = V > LHS，且 b1*y1 + ... bc-1 * yc-1 < LHS。也就是從 b1*y1 開始依序累加，累加到第c項 bc*yc 開始，累加的值首次超過 LHS。
6.  (p1+p2+p3+ ... + pm) + (q1+q2+q3+...+qn) 最小值即為 {yc - (V-LHS)/bc} + (yc+1 +...+ yn)。也就是我們將 bc 以後的每一個位置的重量全部抽掉拿走，然後調整 bc 位置對應的重量，使得左右力矩平衡，且左右力矩大小都是 LHS。如此扣掉的總重量會最少。
7. 同理，若 RHS 較小，算法跟上述一樣，只是 LHS 和 RHS 的角色互換。

證明：
第 6 項中，整個問題可以先想像為 fractional knapsack problem，有若干物品其單位重量的價值為 b1, b2, b3, ...，每個物品重量各為 y1, y2, y3, ...，要配成總價值為 LHS，各物品可拿部分，最多能用到多少重量？

明顯可採用貪婪演算法，單位重量最少價值的物品先拿來配成 LHS 的值，等低價值的物品用完，再拿高價值的物品。

基本想法為：選擇下一個物品來扣值時，我們都要盡量讓扣值速度緩慢，才能讓重量變多。如同一塊餅乾，先給咬小口的螞蟻吃，小螞蟻吃飽了，再給咬大口的動物吃，總計會咬比較多口。