（本文長度：3958個字；預計閱讀時間：10分鐘）
揹包（貪心策略）
揹包問題本質上即轉載問題，通常是在一定條件限制範圍內要求我們尋求最佳的裝載方式獲取最佳的利益。所以普通的揹包問題我們可以通過貪心算法來尋求最佳收益。
我們通過一個大家都耳熟能詳的故事來說明貪心算法在普通揹包問題中的應用。我們要講的就是“阿里巴巴和四十大盜”的故事。
有一天，阿里巴巴趕著毛驢上山砍柴。下山的時候，遠遠看見一股塵煙，瀰漫著直上天空，朝他捲來。靠近之後，他才看清是一對人馬，他們一共四十人，個個身強力壯、行動敏捷。一個首領模樣的人揹著沉重的鞍袋，從叢林中走到一個巨石前，喃喃說道：“芝麻開門”，神奇的事情發生了，大石前突然出現一道寬闊的道路，於是強盜們魚貫而入。阿里巴巴待在樹上觀察著，直到他們走得無影無蹤後，才從樹上下來。他大聲喊道：“芝麻開門！”，洞門立即打開，他小心翼翼地走進去，一下驚呆了！山洞裡堆滿了金銀珠寶。阿里巴巴想讓鄉親們開開眼界，見識一下寶物，他想一個寶物拿一個，如果太重就用鑿子鑿開，但毛驢的裝載能力是有限的，怎樣才能用驢子運走最大價值的財寶分給窮人呢？
問題分析
假設山洞中有n種寶物，每種寶物有一定重量w和相應的價值v，毛驢運載能力有限，只能運走m重量的寶物，一種寶物只能拿一樣，不過寶物是可以分割的。那麼怎麼才能使得毛驢運走的寶物價值最大呢？
對於需要獲得價值最大化的問題，我們可以嘗試貪心策略：
- 每次挑選價值最大化的寶物裝入揹包，得到的結果是否最優？
- 每次挑選重量最小的寶物裝入，能否得到最優解？
- 每次挑選單位重量價值最大的寶物，能否價值最高？
想一想，如果選價值最大的寶物，但重量非常大，是不行的，因為裝載能力有限，所以策略1不合適；如果選重量小的寶物，但可能價值也很小，所以也不能在總重限制的情況下保證價值最大，所以策略2也不合適；而策略3每次選擇單位重量價值最大的，也就是性價比（價值/重量）最高的寶物，如果可以達到運載重量m，那麼總價值一定是最大的。
寶物清單
樣例
輸入
第一行是寶物數量n和最大裝載能力m，之後n+1行分別是每個寶物的重量w和價值v
<code>10 30 4 3 2 8 9 18 5 6 5 8 8 20 5 5 4 6 5 7 5 15/<code>
輸出
一行，表示裝載的最大價值
<code>70.5/<code>
示例代碼
<code>#include
#include
#include
using namespace std;
struct Node{
double w; // weight
double v; // value
double p; // value / weight
}nodes[100];
bool cmp(Node a, Node b)
{
return a.p > b.p;
}
int main()
{
double m; // 揹包最大裝載量
int n; // 商品數量
cin >> n >> m;
for (int i = 0; i < n; i ++)
{
double w,v;
cin >> w >> v;
nodes[i].w = w;
nodes[i].v = v;
nodes[i].p = v / w;
}
sort(nodes, nodes+n, cmp); // 按性價比排序
double ans = 0.0;
// 應用貪心策略
for (int i = 0; i < n; i++)
{
if (m > nodes[i].w)
{
m -= nodes[i].w;
ans += nodes[i].v;
}
else
{
// 剩餘的裝載量小於或者等於當前
// 要裝入的寶物的重量，那麼就是
// 最後一次裝載。因為寶物可以分割
// 所以直接用剩餘裝載量乘以寶物的單位價值
// 就是最後能裝入的價值
ans += m * nodes[i].p;
break;
}
}
cout << ans << endl;
return 0;
}/<code>0-1揹包（動態規劃）
還是我們的阿里巴巴和四十大盜的故事，在上面的故事中，如果寶物是不能被分割的，那麼貪心算法還能得到最優解嗎？
下面我們用組數據來試一試
如果我們採用貪心算法，先裝性價比高的，且物品不能分割，剩餘容量如果無法再裝入剩餘物品，不管還有沒有運載能力，算法都會結束。假設我們得揹包裝載能力是10，那麼根據貪心規則，我們將選擇物品1和2，此時揹包剩餘裝載能力是3，無法再裝入剩餘寶物，裝載的總價值是31。但實際上，如果我們選擇寶物2和3，則正好達到裝載能力，得到的最大價值是34。所以在物品無法分割，沒有裝滿的情況下，貪心算法並不能得到最優解，僅僅是最優解的近似解。
對於物品可以分割的裝載問題我們稱之為揹包問題， 物品不可分割的裝載問題我們稱之為0-1揹包問題。
那麼對於0-1揹包問題我麼怎麼得到最優解呢？
最簡單的算法就是一個一個的組合都嘗試一遍。為了便於說明，我們把數據簡化一下
假設揹包的裝載能力是：9
3個寶物，我們可以得到的組合如下：
我們把所有可能的組合都列出來，可以發現，組合3的裝載方式能得到最大價值。
3個物品可能的組合方式有8種，如果是4種寶物，則有16種組合形式，每增加一個寶物，組合數都會翻倍，這種方式的時間複雜度是O(2^n)，非常非常慢！只要寶物數量多到一定程度，這種算法就行不通。那麼如何找到最優解呢？答案就是：
動態規劃動態規劃
動態規劃（Dynamic Programming）, 是一種通過先解決子問題，再逐步解決大問題的算法。對於揹包問題，我們先解決小揹包問題，再逐步解決大揹包問題。
動態規劃這個名字挺唬人的，其實本質上是一個記錄狀態變化的表格。每個動態規劃算法都是從一個表格開始的，對應前面的揹包問題的表格如下：
行，我們來表示新增加需要裝載的寶物；列，我們用來表示不同裝載能力的揹包，第1列是裝載能力為1的揹包，最後一列就是裝載能力為9的揹包。第1列和最後一列之間是裝載能力遞增的揹包。最終，第3行，第9列格子中的計算結果就將是我們尋求的答案。一開始，表格是空的，我們先來填充第1行。
寶物1
第1行對應著寶物1，這意味著我們要決定是否要將寶物1裝入揹包中，以期獲得價值最高的寶物組合。第1行的第1個單元格表示的揹包容量是1，寶物1的重量是3，很明顯裝不下。第2格揹包容量2，也裝不了，第3格揹包容量3，正好等於寶物1的重量，可以裝下。此時的揹包什麼都沒有，我們選擇裝下寶物1，那麼容量為3的揹包此時裝載的寶物價值是15。
與這個單元格一樣，每個單元格都可以包含當前可以裝下的所有寶物。接下來的單元格所表示的揹包容量都比揹包3大，所以都可以輕鬆的裝下寶物1。
我們的目標是找到裝載能力是9的揹包最大能裝載的價值是多少，但是裝載能力是1，2，3...等的揹包也被我們納入考慮範圍，是不是很奇怪？我們前面說，動態規劃是從解決小問題開始，逐步解決大問題的，所以這裡的小揹包將幫助我們解決大揹包的問題。接著往下看，很快你就會明白了。
現在只是第1行，只有寶物1可以選擇，之後我們將逐行增加寶物，讓選擇豐富起來。
寶物2
現在我們來到表格的第2行，增加一個可以拿走的寶物2。每一行可以裝進揹包的寶物都為當前行的寶物以及之前各行的寶物。寶物2的重量是4，因此，揹包1，2都裝不下，揹包3只能裝下寶物1，也裝不下寶物2，而從第4個揹包開始，可以裝下寶物2。
如上圖所示，揹包3只能裝寶物1，裝載的價值是15，揹包4可以裝載寶物1或者寶物2，那麼應該裝哪個呢？
根據此單元格上一行的數據，我們知道揹包4目前為止裝載的最大價值是15，那麼我們先將15填入此單元格，15是裝載的最大價值麼？不一定，因為我們還有寶物2可以選擇，而同時揹包4也是可以裝載寶物2的。裝載完寶物2後，揹包4裝滿，此時價值是16，顯然16大於15，我們應該在揹包4中裝入寶物2。
接下來，揹包5也可以裝下寶物1或者寶物2。根據上一行的數據，我們還是讓揹包5先裝寶物1，此時裝載價值是15，然後我們再嘗試裝寶物2。拿出寶物1，裝入寶物2，此時裝載的價值是16，揹包還剩餘容量1（5 - 4 = 1），根據表格，我們可以知道容量1的揹包是啥也裝不了的，所以剩餘的1個空間是無法增加裝載價值的。最終裝載寶物2的方案最大價值是16（寶物2的價值） + 0（剩餘空間的最大裝載價值）= 16。顯然16比15大，所以揹包5的選擇也是裝載寶物2，最大裝載價值是16。揹包6的計算結果同揹包5。
然後是揹包7。揹包7的初始最大裝載價值同此單元格的上一行，是15。根據揹包5的計算方式，如果選擇裝載寶物2的話，揹包7裝入寶物2後，裝載的價值是16，剩餘空間是3。根據表格可以知道，空間3的揹包可以裝載的最大價值是15（裝入寶物1），所以此時揹包7可以裝載價值是
16（寶物2的價值） + 15（剩餘空間的最大裝載價值） = 31。31大於15，所以揹包7可裝載的最大價值是31。
發現沒有？在計算大揹包的裝載價值的時候，我們利用了之前小揹包的最大裝載價值結果（存儲在表格中），並動態更新了表格的數據。沒錯，這就是動態規劃的秘密，也就是動態規劃之所以稱為動態規劃的原因啦！
根據上面的計算方式，我們可以很快的填滿這個表格，最終表格數據應該如下圖：
最終計算出來裝載能力9的揹包可以裝載的最大化價值是33。
現在我們來總結一下計算每個揹包的最大裝載價值的方法並抽象成公式便於程序實現。
我們計算每個單元格中的最大價值的時候，實際上是將此單元格的上一行單元格中的值與當前單元格所在行對應的寶物價值加上剩餘空間的價值之和做比較，取其中價值大的作為此單元格的最大裝載價值。
如果我們將這個表格命名為dp，用i表示行，j表示列，那麼可以得到公式：
<code>dp[i][j] = max( dp[i-1][j]/*上一行單元格的值*/, 當前寶物的價值 + dp[i-1][j-當前寶物的重量]/*剩餘空間的價值*/ )/<code>
我們稱這種解決動態規劃問題的公式為狀態轉移方程。解決動態規劃問題的計算關鍵就是狀態轉移方程，如果說表格是動態規劃算法的骨，那麼狀態轉移方程就是它的魂。所以能總結出一個DP問題的狀態轉移方程，就相當於拿到了解決該問題的鑰匙。
下面我們在前面貪心策略的代碼上做修改，實現DP算法來解決上面的問題
輸入
第1行n和m，分別表示寶物數量和揹包裝載能力。第2行到n+1行，每行2個數，分別是每個寶物的重量和價值
<code>3 9 3 15 4 16 6 18/<code>
輸出
輸出1行，為揹包能裝載的最大價值
<code>33/<code>
示例代碼
<code>#include
#include
#include
#include
using namespace std;
// 寶物屬性的結構體
struct Node{
double w; //重量
double v; // 價值
double p; // 性價比
}nodes[10];
int n; // 寶物數量
double m; // 揹包載重
double dp[100][100]; // 動態規劃的表格
int cmp(Node a, Node b)
{
return a.p > b.p;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
double w,v;
cin >> w >> v;
nodes[i].w = w;
nodes[i].v = v;
nodes[i].p = v / w;
}
sort(nodes, nodes + n, cmp); // 將寶物按性價比排序。實際上是否排序並不影響結果
// 狀態轉移方程的實現
for (int i = 0; i < n; i++) // 行，不同的寶物
{
for (int j = 1; j <= m; j++) // 列，不同容量的揹包
{
if (i == 0) // 第一個寶物
{
if (nodes[i].w <= j)
{
dp[i][j] = nodes[i].v;
}
}
else
{
dp[i][j] = dp[i-1][j];
int col = j - nodes[i].w; // 隱含了數據類型轉換
if (col < 0)
continue;
if (nodes[i].v + dp[i-1][col] > dp[i][j])
{
dp[i][j] = nodes[i].v + dp[i-1][col];
}
}
}
}
int c = ceil(m);
cout << dp[n-1][c] << endl;
return 0;
}/<code>
