动态规划——01背包问题

</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.《挑战程序设计竞赛》

推荐阅读更多精彩内容