背包问题研究了好几天，总算是有点头绪了，今天我就把我学到的背包问题整理一下，供各位大佬交流学习，直接开始：
目录：
1、数组递推
2、完全背包
3、01背包
4、后面的等我搞懂了再更...
1、数组递推
上次的文章里面我提到了记忆化搜索，并给出了优化算法，今天我来写一写实际中用得更多的实现方法：数组递推。
//上次问题的数组递推化
f[1] = f[2] = f[3] = 5; f[4] = f[5] = 8;
for (int i = 6; i <= n; ++i)
{
f[i] = min(f[i - 3] + 5, f[i - 5] + 8);
}
其实数组递推的方法很简单，我们需要开一个很大的数组，然后按照某种顺序（通常是多重循环）进行转移就行了。相当于将记忆化搜索中的递归进行了展开。
关于数组递推和记忆化搜索的选择：
1、记忆化搜索是自顶向下的，比较符合直觉，不需要考虑转移的顺序，使用的时候比较容易。但是它使用的是递归，缺点是时间复杂度和空间复杂度都会很高，不容易调试。
2、数组递推的优势在于代码简练，常数小，可以进行空间优化等，它的缺点在于需要确定转移顺序，而且只适用于稠密的状态（不然会计算很多稠密的状态）
大部分时候，我们把状态转移方程写出来之后其实数组递推就很好写了，所以我以后数组递推的程序会写的多一点。
2、完全背包
有一个问题描述：考虑有n种物品，第i种物品的每个重量为wi，价值为vi，有无限多个。我们手头有一个大小为m的背包，需要算出能装下的最大总价值。
和昨天的问题有些类似，我们设f(i)表示大小为i的背包最多能装的价值，那么可以得到一个转移方程：f(i) = max{f(i-w1) + v1 , f(i-w2) + v2 , f(i-wn) + vn}，如果追求简洁，可以写成：f(i) = max{f(i - wj) + vj}，1<=j<i 。初始条件为f(0) = 0
思考一下如何用代码实现：
for(int i = 0 ; i <= m ; ++i) //容量迭代
{
for(int j = 1 ; j <= n ; ++j) //枚举物品
{
if(i >= w[j]) // 背包当前的容量存得下
f[i] = max(f[i] , f[i - w[j]] + v[i]);
}
}
交换两重循环的顺序也是可以的
for(int i = 1 ; i <= n ; ++i) //枚举物品
{
for(int j = 0 ; j <= m ; ++j) //容量迭代
f[j] = max(f[j] , f[j-w[i]] + v[i]);
}
复杂度分析：我们总共有m个状态，每个状态需要转移n次，故最终的复杂度为O(nm)。
3、01背包
将问题稍作改动：考虑有n种物品，第i种物品的重量为wi，价值为vi，每种物品只有一件。有一个大小为m的背包，需要算出能装下的最大总价值。
问题分析：我们不能再像刚刚那样设计状态了，因为每个物品取过之后就不能再取，所以状态还需要记录物品的相关信息。
考虑如何将问题转化为规模更小的子问题，对于某个物品，再最终的方案中要么取，要么不取，于是我们对这两种情况来分类讨论，转化为子问题：
1、如果没有取第n个物品，那么相当于只有前n-1个物品，背包大小相同的子问题
2、如果取了第n个物品，那么相当于只有前n-1个问题，背包大小减去wn的子问题，再在他的答案上再加上vn的价值。
在两种情况中取价值更高的，得到答案。
那么我们的状态转移方程就已经很好写了：
设f(i,j)表示使用编号为1~n的物品，背包容量为j时的最大值，有转移方程：f(i , j) = max{f(i - 1 , j) , f(i - 1 , j - wi) + vi }
初始条件为：f(0,*) = 0； 代码实现如下：
for(int i = 1 ; i <= n ; ++i)
for(int j = 0 ; j <= m ; ++j)
{
if(j<w[i])
f[i-1][j];
else
f[i][j] = max{f[i-1][j] , f[i-1][j-w[i]] + v[i]};
}
时间复杂度为O(nm)。这段代码的空间复杂度也达到了O(nm)，在一些问题中无法接受，我们尝试来优化它。
滚动数组：看刚才的代码我们可以知道，每个f[i][j]在转移的时候只用到了f[i-1][*]。也就是说比i-1更小的再也不会被用到 。如果把f看成一张二维的表格，那么只有两行的格子时活跃的，基于这一思想，我么可以只保存这两行，具体实现如下：
int p = 1, q = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j <= m; ++j)
{
if (j < w[i]) f[p][j] = f[q][j];
else f[p][j] = max(f[q][j], f[q][j - w[i]] + v[i]);
}
swap(p, q);
}
继续刚才的思路：把f看成一张二维的表格，那么每个格子在转移时 只会用到上一行中在它左侧的格子。如果我们调整一下转移的顺序，每 一行从右往左进行更新（j从大到小），那么“活跃”的格子就正好只有 上一行的左半部分以及这一行的右半部分。那么实际上我们只需要保存这些活跃的格子的状态就行了。
for (int i = 1; i <= n; ++i)
{
for (int j = m; j >= w[i]; --j)
{ // 倒序，倒序，倒序
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
}
以上就是01背包的所有内容了，我的课程设计有一个题目选了01背包的问题，下面我来好好分析一下：（题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2546 ）
读懂题意之后就可以开始将它转换成已知问题了，首先如果想要卡上的余额最少，使用贪心的思想就是将最后的5块钱取购买最贵的物品，所以我们就可以将它转换为容量是余额-5，菜的种类为n-1的01背包问题。
首先我们要列出状态方程：f(i , j) = max{f(i - 1 , j) ， f(i - 1)(j - p[i]) + p[i]};
有了状态转移方程之后，我们写代码就很有底气了，我写的代码如下，供大家交流学习。
//留下5块钱去买最贵的菜，则菜数变成 n - 1 , 卡上的余额为m - 5 转换成01背包问题
//状态转移方程：f(n, m) = max{f(n - 1, m) , f(n - 1 , m - p[n]) + p[n]}
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int p[1005];
int f[1005][1005];
int main()
{
int i , j , m , n;
while(scanf("%d" , &n) && n) //对于读入正确的每组数据:
{
for(i = 1 ; i <= n ; ++i)
cin >> p[i];
sort(p + 1 ,p + n + 1); //为了找到最大值 p[n-1]即为价格最大的菜
cin >> m;
for(i = 0 ; i <= m-5 ; i++) //初始化条件 , 不然可能影响下组数据
f[0][i] = 0;
if(m < 5)
cout << m << endl; //钱数少于5啥也买不了
else
{
for(i = 1 ; i <= n - 1 ; ++i) //01背包的模板代码
{
for(j = 0 ; j <= m - 5 ; ++j)
{
if(j < p[i])
f[i][j] = f[i-1][j]; //选不了
else
f[i][j] = max(f[i-1][j] , f[i-1][j-p[i]] + p[i]);
}
}
cout<<m - f[n-1][m-5] - p[n]<<endl;
}
}
return 0;
}
Comments | NOTHING