（本文长度：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>
