前言
简单写一下算法设计与分析这门课的一次实验
原题要求是用0-1背包来做,但是老师要求用完全背包来做!
一、完全背包与0-1背包有什么区别?
0-1背包,顾名思义对于每件物品只能拿1次或者0次;而完全背包对于每件物品的拿取没有次数限制。
二、二维费用背包
二维费用背包是对于每件物品的拿取要付出两项代价,如:重量和体积。
三、0-1背包
理解0-1背包对我们理解其他背包问题十分重要,首先说一下0-1背包。
问题描述:
有n件物品,背包的最大承重是W,每个物品的重量是c[i],价值为v[i];定义状态f[i][w]为当前包内的可承重为w时,在前i件物品内选取得到的最大价值;
对于状态f[i][w]有两种选择:
- 在背包当前承重允许的情况下选择第i件物品,那么原问题规约为在前i-1件物品选取得到重量不超过w-c[i]的最大价值的子问题,此时f[i][w]=f[i-1][w-c[i]]+v[i];
- 不选择第i件物品,那么原问题规约为在前i-1件物品中选取得到重量不超过w的最大价值的子问题,此时f[i][w]=f[i-1][w];
所以可以得到相应的状态转移方程:
f[i][w]=max(f[i-1][w],f[i-1][w-c[i]+v[i])
所以可以得到0-1背包问题的核心代码:
for(int i=1;i<=n;i++){
for(int w=c[i];w<=W;w++){
f[i][w]=max(f[i-1][w],f[i-1][w-c[i]]+v[i]);
}
}
这里时间与空间复杂度均为O(V*n);时间复杂度已经无法继续优化,但空间复杂度可以。通过观察发现,类似滚动数组原理,可以将f[i][w]压缩成f[w]的一维数组,只需要维护这样的一维数组即可。
所以上面代码变成下面这样:
for(int i=1;i<=n;i++){
for(int w=W;w>=c[i];w--){
f[w]=max(f[w],f[w-c[i]]+v[i]);
}
}
相信已经有小伙伴发现了这两段代码的区别不仅仅是数组了。第一段代码中第二层循环是正序的,而第二段代码中第二层循环变成逆序了。这里便是需要注意的地方。下面将给出说明:
当f是二维数组时,不管f[i][w]做出哪种选择都依赖上一行i-1行的结果,这时只要直接获取即可。当f为一维数组时,此时f数组还未刷新即对应二维数组i-1行,如果循环是顺序的话,当f[w]刷新后,如果后面的f[w’]需要i-1行的f[w]时,此时f[w]已经是i行的f[w],那么就会出错,因此需要逆序循环,这时候需要访问的f[w]都是未刷新前的。
四、完全背包
完全背包与0-1背包的区别已经说过,不再赘述。
对于f[i][w]有两种选择:
- 不选择当前的第i件物品,原问题规约为在前i-1件物品中选取,此时f[i][w]=f[i-1][w];
- 选择当前第i件物品,原问题规约为在前i件物品中选取,此时f[i][w]=f[i][w-c[i]]+v[i];
f[i][w]=max(f[i-1][w],f[i][w-c[i]]+v[i])
这里直接给出压缩成一维数组后的核心代码
for(int i=1;i<=n;i++){
for(int w=c[i];w<=W;w++){
f[w]=max(f[w],f[w-c[i]]+v[i]);
}
}
这里的第二层循环为什么是正序。这里做出解释:因为完全背包的特点,当选择第i件物品时,问题会变成在前i件物品中选取,不会变成0-1背包那样在前i-1件物品中选取,因此当计算f[w]时可能需要当前已经刷新后的f[w’],即第i行的数据。
五、二维费用的完全背包问题
回到本次实验:
本次实验是二维费用下的完全背包问题。与一维相比也就是多了一层循环。该实验的完整代码如下:
//定义物品数据结构
struct item{
int w;//重量
int c;//体积
int v;//价值
};
int KnapsackProblem(item x[],int n,int W,int V){//物品数组,物品数量,重量上限,体积上限
//初始化
dp[0][0]=0;
for(int i=1;i<=n;i++){
for(int w=x[i].w;w<=W;w++){
for(int c=x[i].c;c<=V;c++){
dp[w][c]=max(dp[w][c],dp[w-x[i].w][c-x[i].c]+x[i].v);
}
}
}
return dp[W][V];
}
KnapsackProblem()函数的时间复杂度为O(nVW);
小结
关于背包问题有很多人的讲解。这是笔者第一次写博客,主要是自己的一些理解,如果有错误的地方希望能够给予指正。如果有其他建议也可以添加笔者的QQ:2736664064进行交流。