lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>3</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'>5</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'>3</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'>2</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'>5 (</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'>9 )</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'>1</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'>5</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'>1</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'>3</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'>2</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'>5 (</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'>11 )</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'>3</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'>4</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'>5</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'>1</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'>5</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'>1</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'>3</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'>4</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'>5 (</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'>9) </span><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.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'>v</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'>v </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'>v </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'>d </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.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 lang=EN-US>3</span></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'>-2 [0/1</span></b><b><spanstyle='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>背包問題</span></b><b><span lang=EN-US style='font-size:10.0pt;font-family:Arial;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>]</span></b><spanlang=EN-US style='font-size:10.0pt;font-family:Arial;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'> </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'>1 3 . 4</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'>0 / 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'>x</span></i><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;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'>n</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'>i </span></i><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><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>2</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，<spanlang=EN-US>.，</span></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><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><i><span lang=EN-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><span lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>1 </span><spanlang=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'>2</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'>3</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，<span lang=EN-US>.，</span></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: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><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>x</span></i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>1 </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'>c</span></i><spanlang=EN-US 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'>w</span></i><spanlang=EN-US style='font-size:5.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-USstyle='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>r</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'>&Icirc;</span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>{<i>c</i></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'>c</span></i><span lang=EN-USstyle='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'>w</span></i><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>1 </span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>} </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><spanlang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>r </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><span lang=EN-USstyle='font-size:5.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><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>0</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'>1</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'>[<i>x</i></span><span lang=EN-USstyle='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>2 </span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，<span lang=EN-US>.，</span></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;