</br> <a>背包问题(Knapsack problem)</a>是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
01背包问题就是背包问题中最经典的题目之一，常被程序设计竞赛选为母题，是每个选手必须掌握的重要知识点。
</br>
<a>01背包问题</a>
<pre></br>有n个质量和价值分别为w1，vi的物品。从这些物品中挑选出总质量不超过W的物品，求所有挑选方案中价值总和的最大值</br></pre>
<a>解题思路</a>
首先尝试用最朴素的方法：枚举每一种可能来比较最大值。
所以，第一步，运用动态规划的思想列出本题的动规方程：
1.设 f (i , j) 为计算从i到n这n-i个物品质量总和不大于j的价值最大值。
2.那么对于每一个物品，都有取或不取两种状态，所以很快就可以列出递归方程：<pre>f (i, j) = max{f(i + 1, j - w[i]) + v[i], //取此物品</br> f(i + 1, j)} //不取此物品</pre>
3.So,就可以据此写出递归代码
<pre>
<code>#define MAXN 1000</code>
<code>
int n, W;//物品总数和最大质量
int w[MAXN+1], v[MAXN+1];//物品质量和价值
int f(int i, int j)//前i个物品，价格不超过j的最大值
{
int ret;
if (i >= n)//没有多余物品了
return 0;
if (v[i] > j)//要求质量不够拿此物品
ret = f(i+1, j);
else
//比较那或不拿那个价值大
ret = max(f(i+1, j-v[i])+(v[i]*w[i]), f(i+1, j));
return ret;
}
</code></pre>
但是，如果你对时间复杂度有一些了解，就很快会发现一个问题：</br>如果这样写代码，时间复杂度就是O(2^n)。明显会超出时间限制。[关于时间复杂度可以到http://blog.csdn.net/flyyyri/article/details/5154618做一下了解]
</br></br>
所以，再次利用动态规划的重要思想：记忆化搜索，来优化算法：
<pre>
<code>#define MAXN 1000</code>
<code>
int n, W;//物品总数和最大质量
int w[MAXN+1], v[MAXN+1];//物品质量和价值
int dpmem[MAXN+1][MAXN+1];//记忆数组
int f(int i, int j)//前i个物品，价格不超过j的最大值
{
int ret;
if(dpmem[i][j] != -1)//是否已经计算过此结果
return dpmem[i][j];//返回已计算结果
if (i >= n)//没有多余物品了
return 0;
if (v[i] > j)//要求质量不够拿此物品
ret = f(i+1, j);
else
//比较那或不拿那个价值大
ret = max(f(i+1, j-v[i])+(v[i]*w[i]), f(i+1, j));
dpmem[i][j] = ret;//记录结果
return ret;
}
</code></pre>需要注意的是，在使用前，需要对dpmem数组初始化（我这里是全初始化成-1来代表还未计算），可以用memset实现。
顺便附一组测试数据以供参考：
测试数据：
n = 4, m = 10
w[i] = {2, 3, 2, 1};
v[i] = {4, 8, 10, 5};
结果：
27
引用：
1.百度百科
2.《挑战程序设计竞赛》
