01背包笔记
- 01背包
- 问题描述
已知:有一个容量为V的背包和N件物品，第i件物品的重量是weight[i]，收益是cost[i]。
限制:每种物品只有一件，可以选择放或者不放
问题:在不超过背包容量的情况下，最多能获得多少价值或收益
相似问题:在恰好装满背包的情况下，最多能获得多少价值或收益
这里，我们先讨论在不超过背包容量的情况下，最多能获得多少价值或收益。
- 基本思路
01背包的特点:每种物品只有一件，可以选择放或者不放
状态转移方程
f[i][v] = max(f[i – 1][v],f[i – 1][v – weight[i]] + cost[i])
- 分析
考虑我们的子问题，将前i件物品放到容量为v的背包中，若我们只考虑第i件物品时，它有两种选择，放或者不放。
1) 如果第i件物品不放入背包中，那么问题就转换为：将前i – 1件物品放到容量为v的背包中，带来的收益f[i – 1][v]
2) 如果第i件物品能放入背包中，那么问题就转换为：将前i – 1件物品放到容量为v – weight[i]的背包中，带来的收益f[i – 1][v – weight[i]] + cost[i]
- 代码
#include <iostream>
using namespace std;
const int N = 3;//物品个数
const int V = 5;//背包最大容量
int weight[N + 1] = {0,3,2,2};//物品重量
int value[N + 1] = {0,5,10,20};//物品价值
int f[N + 1][V + 1] = {{0}};
int Max(int x,int y)
{
return x > y ? x : y;
}
/*
目标：在不超过背包容量的情况下，最多能获得多少价值
子问题状态:f[i][j]:表示前i件物品放入容量为j的背包得到的最大价值
状态转移方程:f[i][j] = max{f[i - 1][j],f[i - 1][j - weight[i]] + value[i]}
初始化:f数组全设置为0
*/
int Knapsack()
{
//初始化
memset(f,0,sizeof(f));
//递推
for (int i = 1;i <= N;i++) //枚举物品
{
for (int j = 0;j <= V;j++) //枚举背包容量
{
f[i][j] = f[i - 1][j];
if (j >= weight[i])
{
f[i][j] = Max(f[i - 1][j],f[i - 1][j - weight[i]] + value[i]);
}
}
}
return f[N][V];
}
int main()
{
cout<<Knapsack()<<endl;
return 1;
}
- 效率分析
此算法的时间复杂度为O(N*V)，空间复杂度也为O(N*V)。其中，N 表示物品个数，V 表示背包容量这里，时间复杂度不可以在优化了，但是空间复杂度可以继续优化到O(V)
- 优化空间复杂度
上述的方法，我们使用二维数组 f[i][v] 保存中间状态，这里我们可以使用一维数组f[v]保存中间状态就能得到结果
- 分析
我们现在使用f[v]保存中间状态，我们想要达到的效果是，第i次循环后，f[v]中存储的是前i个物体放到容量v时的最大价值
在回顾下之前讲过的状态转移方程：
f[i][v] = max(f[i – 1][v],f[i – 1][v – weight[i]] + cost[i])
我们可以看到，要想得到 f[i][v]，我们需要知道 f[i – 1][v] 和 f[i – 1][v – weight[i]]，由于我们使用二维数组保存中间状态，所以可以直接取出这两个状态。
当我们使用一维数组存储状态时，f[v]表示，在执行i次循环后(此时已经处理i个物品)，前i个物体放到容量v时的最大价值，即之前的f[i][v]。与二维相比较，它把第一维隐去了，但是二者表达的含义还是相同的，只不过针对不同的i，f[v]一直在重复使用，所以，也会出现第i次循环可能会覆盖第i – 1次循环的结果。
为了求f[v],我们需要知道，前i – 1个物品放到容量v的背包中带来的收益，即之前的f[i – 1][v] 和 前i – 1件物品放到容量为v – weight[i]的背包中带来的收益，即之前的f[i – 1][v – weight[i]] + cost[i]。
难点：由于我们只使用一维数组存储，则在求这两个子问题时就没有直接取出那么方便了，因为，第i次循环可能会覆盖第i – 1次循环的结果。
现在我们来求这两个值
1）前i – 1个物品放到容量v的背包中带来的收益，即之前的f[i – 1][v] ：
由于，在执行在i次循环时，f[v]存储的是前i个物体放到容量v时的最大价值，在求前i个物体放到容量v时的最大价值(即之前的f[i][v])时，我们是正在执行第 i 次循环，f[ v ]的值还是在第 i – 1 次循环时存下的值，在此时取出的 f[ v ]就是前i – 1个物体放到容量v时的最大价值，即f[i – 1][v]。
2）前i – 1件物品放到容量为v – weight[i]的背包中带来的收益，即之前的f[i – 1][v – weight[i]] + cost[i]
由于，在执行第i次循环前，f[0 ~ V]中保存的是第i – 1次循环的结果，即是前i – 1个物体分别放到容量0 ~ V时的最大价值，即f[i – 1][0 ~ V]。
则，在执行第i次循环前，f 数组中v – weight[i]的位置存储就是我们要找的 前i – 1件物品放到容量为v – weight[i]的背包中带来的收益 (即之前的f[i – 1][v – weight[i]])，这里假设物品是从数组下标1开始存储的。
- 逆序枚举容量的原因
注意一点，我们是由第 i – 1 次循环的两个状态推出 第 i 个状态的，而且 v > v – weight[i]，则对于第i次循环，背包容量只有当V..0循环时，才会先处理背包容量为v的状况，后处理背包容量为 v-weight[i] 的情况。
具体来说，由于，在执行v时，还没执行到v – weight[i]的，因此，f[v – weight[i]]保存的还是第i – 1次循环的结果。即在执行第i次循环 且 背包容量为v时，此时的f[v]存储的是 f[i – 1][v] ，此时f[v-weight[i]]存储的是f[i – 1][v-weight[i]]。
相反，如果在执行第 i 次循环时，背包容量按照0..V的顺序遍历一遍，来检测第 i 件物品是否能放。此时在执行第i次循环 且 背包容量为v时，此时的f[v]存储的是 f[i – 1][v] ，但是，此时f[v-weight[i]]存储的是f[i][v-weight[i]]。
因为，v > v – weight[i]，第i次循环中，执行背包容量为v时，容量为v – weight[i]的背包已经计算过，即f[v – weight[i]]中存储的是f[i][v – weight[i]]。即，对于01背包，按照增序枚举背包容量是不对的。（其实就是完全背包）
#include <iostream>
using namespace std;
const int N = 3;//物品个数
const int V = 5;//背包最大容量
int weight[N + 1] = {0,3,2,2};//物品重量
int value[N + 1] = {0,5,10,20};//物品价值
int f[V + 1] = {0};
int Max(int x,int y)
{
return x > y ? x : y;
}
/*
目标：在不超过背包容量的情况下，最多能获得多少价值
子问题状态:f[j]:表示前i件物品放入容量为j的背包得到的最大价值
状态转移方程:f[j] = max{f[j],f[j - weight[i]] + value[i]}
初始化:f数组全设置为0
*/
int Knapsack()
{
//初始化
memset(f,0,sizeof(f));
//递推
for (int i = 1;i <= N;i++) //枚举物品
{
for (int j = V;j >= weight[i];j--) //枚举背包容量,防越界，j下限为 weight[i]
{
f[j] = Max(f[j],f[j - weight[i]] + value[i]);
}
}
return f[V];
}
int main()
{
cout<<Knapsack()<<endl;
return 1;
}
- 初始化的细节问题
求最优解的背包问题时，有两种问法：
1)在不超过背包容量的情况下，最多能获得多少价值
2)在恰好装满背包的情况下，最多能获得多少价值
主要的区别为是否要求恰好装满背包。但这两种问法的实现方法是在初始化的时候有所不同。
1)恰好装满背包的情况：使用二维数组f[i][v]存储中间状态，其中第一维表示物品，第二维表示背包容量
初始化时，除了f[i][0] = 0（第一列）外，其他全为负无穷。
原因：初始化 f 数组就是表示：在没有任何物品可以放入背包时的合法状态。对于恰好装满背包，只有背包容量为 0（第一列），可以什么物品都不装就能装满，这种情况是合法情况，此时价值为0。其他f[0][v]（第一列）是都不能装满的，此时有容量没物品。而其他位置（除去第一行和第一列的位置），我们为了在计算中比较最大值，也要初始化为负无穷。我们从程序的角度上看，我们只允许装入背包物品的序列的起始位置是从第一列开始，这些起始位置都是合法位置，且能恰好装满的情况收益均为正值，到f[N][V]终止。
注意，我们虽然是求恰好装满，还是需要枚举所有可以装入背包的物品，只要能装入，还需装入，收益有增加。只不过，由于恰好装满的物品的序列肯定是从第一列某行开始的，且之后的收益肯定是正值。对于非恰好装满的物品序列，其实位置肯定是从第一行某位置开始的，由于此时被初始化为负无穷，在和那些恰好装满物品序列带来的价值时，肯定是小的。所以，我们最后能获得最大值。
- 代码
二维数组
#include <iostream>
using namespace std;
const int MinNum = 0x80000000;
const int N = 3;//物品个数
const int V = 5;//背包最大容量
int weight[N + 1] = {0,3,2,2};//物品重量
int value[N + 1] = {0,5,10,20};//物品价值
int f[N + 1][V + 1] = {{0}};
int Max(int x,int y)
{
return x > y ? x : y;
}
/*
目标：在恰好装满背包的情况下，最多能获得多少价值
子问题状态:f[i][j]:表示前i件物品放入容量为j的背包得到的最大价值
状态转移方程:f[i][j] = max{f[i - 1][j],f[i - 1][j - weight[i]] + value[i]}
初始化:f数组全设置为0
*/
int Knapsack()
{
//初始化
for (int i = 0;i <= N;i++) //枚举物品
{
for (int j = 0;j <= V;j++) //枚举背包容量
{
f[i][j] = MinNum;
}
}
for (int i = 0;i <= N;i++)
{
f[i][0] = 0;//背包容量为0时为合法状态
}
//递推
for (int i = 1;i <= N;i++) //枚举物品
{
for (int j = 1;j <= V;j++) //枚举背包容量
{
f[i][j] = f[i - 1][j];
if (j >= weight[i])
{
f[i][j] = Max(f[i - 1][j],f[i - 1][j - weight[i]] + value[i]);
}
}
}
return f[N][V];
}
int main()
{
cout<<Knapsack()<<endl;//输出25
return 1;
}
使用一维数组f[v]存储中间状态，维表示背包容量
初始化时，除了f[0] = 0，其他全为负无穷。
原因：只有容量为0 的背包可以什么物品都不装就能装满，此时价值为0。其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为负无穷了
- 代码
#include <iostream>
using namespace std;
const int MinNum = 0x80000000;//int最小的数
const int N = 3;//物品个数
const int V = 5;//背包最大容量
int weight[N + 1] = {0,3,2,2};//物品重量
int value[N + 1] = {0,5,10,20};//物品价值
int f[V + 1] = {0};
int Max(int x,int y)
{
return x > y ? x : y;
}
/*
目标：在恰好装满背包容量的情况下，最多能获得多少价值
子问题状态:f[j]:表示前i件物品放入容量为j的背包得到的最大价值
状态转移方程:f[j] = max{f[j],f[j - weight[i]] + value[i]}
初始化:f数组全设置为0
*/
int Knapsack()
{
//初始化
for (int i = 0;i <= V;i++)
{
f[i] = MinNum;
}
f[0] = 0;//只有背包容量为0时才是合法状态，由合法状态组成的结果才是合法的
//递推
for (int i = 1;i <= N;i++) //枚举物品
{
for (int j = V;j >= weight[i];j--) //枚举背包容量,防越界，j下限为 weight[i]
{
f[j] = Max(f[j],f[j - weight[i]] + value[i]);
}
}
return f[V];
}
int main()
{
cout<<Knapsack()<<endl;//输出25
return 1;
}
一个常数优化
一维数组描述状态时的伪代码：
for i=1..N //枚举物品
for v=V..0 //枚举容量，从大到小
f[v]=max{f[v],f[v-weight[i]] + cost[i]};
观察可知，对于第i个物品，枚举背包容量下限时，可以到weight[i]为止。
原因
1）对于第i物品，在求f[v]时，需要使用的状态是 v ~ v – weight[i] 这么多，这是由于v取最大容量V时，使用的状态才是v – weight[i]，当v不取最大状态时，使用的状态肯定是在v ~ v – weight[i]之间的。可以到weight[i]为止。
2）在到weight[i]为止时，还可以不进行if判断，担心v – weight[i]是否越界
此时，伪代码为
for i=1..N //枚举物品
for v=V..weight[i] //枚举容量，从大到小
f[v]=max{f[v],f[v-weight[i]] + cost[i]};
注意，对 f 数组，如果是检测第i个物品是否能放入，0 ~ weight[i] – 1的这些位置是不会遍历到的，则此时他们仍表示第i – 1次的状态，即二维的f[i – 1][v]。
优化下界
还可以继续优化下界为
for i=1..N //枚举物品
bound=max{V-sum{weight[i..n]},weight[i]}//确定需要枚举容量的下界
for v=V..bound
f[v]=max{f[v],f[v-weight[i]] + cost[i]};
原因：对于第i次循环（指外循环），对于背包容量v = V(最大)时，对于f[v]的值，其实只要知道f[v-weight[i]]即可。以此类推，对于背包容量为 j 时，我们只需要知道到f[v-sum{weight[j..n]}]即可。