[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] 以下是我的想法。如有錯誤請指正。 假如等號左右兩邊沒有 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 先比較大小。 我們將 RHS 和 LHS 想像成槓桿左右力矩平衡的問題。a1～am 以及 b1～bn 視為力臂，x1~xm 以及 y1~yn 視為各個力臂位置的重量。今槓桿左右力矩不平衡，想抽掉重量，總共抽掉的重量要越少越好。 假設上述條件下，LHS 較小，就令 p1~pm 皆為 0。這是很明顯的，p1~pm 要為 0 才會是最佳解。否則 RHS 勢必要抽掉更多重量才能達到力矩平衡。 令 RHS-LHS = k。 找到 bc，使得 (b1*y1 + ... + bc*yc) = V > LHS，且 b1*y1 + ... bc-1 * yc-1 (p1+p2+p3+ ... + pm) + (q1+q2+q3+...+qn) 最小值即為 {yc - (V-LHS)/bc} + (yc+1 +...+ yn)。也就是我們將 b...