0pt'>&aring;</span><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i</span></i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>=1</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>=<i>t</i></span><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>（</span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>0</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>≤</span><i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i</span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>≤</span><i><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>a</span></i><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i</span></i><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>）。如果</span><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>n </span></i><span lang=EN-USstyle='font-size:10.0pt;font-family:Symbol;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>&aring;</span><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>= 1</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>a</span></i><i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>&lt;<i>t</i></span><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，則輸出適當的錯誤信息。<span lang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal align=left style='text-align:left;text-indent:20.0pt;mso-char-indent-count:2.0;mso-char-indent-size:10.0pt;mso-layout-grid-align:none;text-autospace:none'><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>在這個問題中，限制條件是</span><i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>n </span></i><span lang=EN-US style='font-size:10.0pt;font-family:Symbol;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>&aring;</span><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i</span></i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>= 1</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>=<i>t </i></span><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>且</span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>0</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>≤</span><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i</span><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>≤</span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>a</span><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，</span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>1</span><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>≤</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i</span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>≤</span><i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>n</span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>。而優化函數是</span><i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>n </span></i><span lang=EN-US style='font-size:10.0pt;font-family:Symbol;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>&aring;</span><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i</span></i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>= 1</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>s</span></i><i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>。任何滿足限制條件的一組實數</span><i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>都是可行解，而使</span><i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>n </span></i><span lang=EN-US style='font-size:10.0pt;font-family:Symbol;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>&aring;</span><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i</span></i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>= 1</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>s</span></i><i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>最大的可行解是最優解。<span lang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal align=left style='text-align:left;text-indent:20.1pt;mso-char-indent-count:2.0;mso-char-indent-size:10.05pt;mso-layout-grid-align:none;text-autospace:none'><b><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>例</span></b><b><span lang=EN-USstyle='font-size:10.0pt;font-family:Arial;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>1-2 [</span></b><b><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>裝載問題</span></b><b><spanlang=EN-US style='font-size:10.0pt;font-family:Arial;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>] </span></b><span lang=EN-USstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'><span style="mso-spacerun: yes">&nbsp;</span>有一艘大船準備用來裝載貨物。所有待裝貨物都裝在貨箱中且所有貨箱的大小都一樣，但貨箱的重量都各不相同。設第</span><i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>個貨箱的重量為</span><i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>w</span></i><i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i</span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>（</span><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>1</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>≤</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i</span></i><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>≤</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>n</span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>），而貨船的最大載重量為</span><i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>c</span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，我們的目的是在貨船上裝入最多的貨物。<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal align=left style='text-align:left;text-indent:20.0pt;mso-char-indent-count:2.0;mso-char-indent-size:10.0pt;mso-layout-grid-align:none;text-autospace:none'><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>這個問題可以作為最優化問題進行描述：設存在一組變量</span><i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，其可能取值為</span><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>0</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>或</span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>1</span><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>。如</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>為</span><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>0</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，則貨箱</span><i><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>將不被裝上船；如</span><i><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>為</span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>1</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，則貨箱</span><i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>將被裝上船。我們的目的是找到一組</span><i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，使它滿足限制條件</span><i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>n </span></i><span lang=EN-US style='font-size:10.0pt;font-family:Symbol;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>&aring;</span><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>= 1</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>w</span></i><i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><i><spanlang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>≤</span><i><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>c </span></i><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>且</span><i><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x </span></i><i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </span></i><spanlang=EN-US style='font-size:10.0pt;font-family:Symbol;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>&Icirc; </span><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>{0, 1}, 1 </span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>≤</span><i><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;