算法設計與分析章節(jié)練習(2020.01.12)

根據(jù)優(yōu)先隊列式分支限界法，求下圖中從v1點到v9點的單源最短路徑，請畫出求得最優(yōu)解的解空間樹。要求中間被舍棄的結點用×標記，獲得中間解的結點用單圓圈○框起，最優(yōu)解用雙圓圈◎框起。

考慮使用動態(tài)規(guī)劃方法求解下列問題：
01背包數(shù)據(jù)如下表，求：能夠放入背包的最有價值的物品集合。

如設：V（i，j）——前i個物品中能夠裝入承重量j的背包中的最大總價值。請將如下遞推式填寫完整：

自底向上：按行或列填寫下表。