如何使用整數線性規劃去解決「麥記格到最抵」問題
csp, linearprogramming, math at April 22nd, 2009 by 小影
話說在電鋸裡看到「無聊問題」，除了寫程式去解決這問題，我們還可以把它當成一個 限制滿足問題 (Constraint Satisfaction Problem)，用整數線性規劃 ( Integer Linear Programming) 去解決。在此請讓我大膽試用學了兩個小時的 ILP 來解這問題吧！(因為是初學者，如果有錯還請指正，謝謝！) * * * 首先我們假設只有以下六種貨品： i1 雙層芝士孖堡 i2 至尊漢堡 i3 中薯條 i4 中可樂 i5 雙層芝士孖堡套餐 i6 至尊漢堡套餐 設每種貨品的價格為 p1, p2, ..., p6。 設每種食品的目標數量為 w1, w2..., w6。 設每種貨品的落單量為 x1, x2 ..., x6。( <-- 這是我們想要的答案 ) 1. 設我們想要 1 個芝士孖堡 (w1 = 1)，那我們可得以下方程： x1 + x5 >= w1 = 1 2. 同樣我們想要 1 個至尊漢堡 (w2 ...
