旅行商問題+背包問題--經典問題

問題描述：

• 旅行商問題（Traveling Salesman Problem,TSP）是旅行商要到若幹個城市旅行，各城市之間的費用是已知的，為了節省費用，旅行商決定從所在城市出發，到每個城市旅行一次後傳回初始城市，問他應選擇什麼樣的路線才能使所走的總費用最短？此問題可描述如下：設G=(V,E)是一個具有邊成本cij的有向圖，cij的定義如下，對于所有的i和j，cij>0,若<i,j>不屬于E，則cij=∞。令|V|=n，并假設n>1。 G的一條周遊路線是包含V中每個結點的一個有向環，周遊路線的成本是此路線上所有邊的成本和。
• 旅行商問題（Traveling Saleman Problem，TSP）又譯為旅行推銷員問題、貨郎擔問題，簡稱為TSP問題，是最基本的路線問題，該問題是在尋求單一旅行者由起點出發，通過所有給定的需求點之後，最後再回到原點的最小路徑成本。最早的旅行商問題的數學規劃是由Dantzig（1959）等人提出。　

問題分析

• 旅行商問題要從圖G的所有周遊路線中求取最小成本的周遊路線，而從初始點出發的周遊路線一共有(n-1)!條，即等于除初始結點外的n-1個結點的排列數，是以旅行商問題是一個排列問題。排列問題比子集合的選擇問題通常要難于求解得多，這是因為n個物體有n!種排列。通過枚舉(n-1)!條周遊路線，從中找出一條具有最小成本的周遊路線的算法，其計算時間顯然為O(n!)。

旅行商問題的解法

背包問題

• 背包問題(Knapsack problem)是一種組合優化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量内，我們如何選擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合适的物品放置于給定背包中。
• 也可以将背包問題描述為決定性問題，即在總重量不超過W的前提下，總價值是否能達到V？

題目

• 有N件物品和一個容量為V的背包。第i件物品的費用是c，價值是w。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

基本思路

• 這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。
• 用子問題定義狀态：即f[v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀态轉移方程便是：f[v]=max{f[v],f[v-c]+w}。
• 這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。是以有必要将它詳細解釋一下：“将前i件物品放入容量為v的背包中”這個子問題，若隻考慮第i件物品的政策（放或不放），那麼就可以轉化為一個隻牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為“前i-1件物品放入容量為v的背包中”；如果放第i件物品，那麼問題就轉化為“前i-1件物品放入剩下的容量為v-c的背包中”，此時能獲得的最大價值就是f [v-c]再加上通過放入第i件物品獲得的價值w。

C/C++基本文法學習

STL

C++ primer