文章目录
- 1. 01 背包问题
- 1.二维解决
- 2. 一维优化
- 2. 完全背包问题
- 1.暴力3 for.
- 2. 二维优化
- 3. 一维优化
- 3. 多重背包问题Ⅰ.
- 1. 二维解决
- 2. 一维优化
- 4. 多重背包问题Ⅱ
- 5. 混合背包问题
- 6. 二维费用背包问题
- 7. 分组背包问题
背包问题是动态规划中非常典型的一些题，本篇文章记录总结一下在学习过程中所遇到的一些背包问题。
其实主要就是3种,01,完全,多重背包问题，这三种详细一些，认真搞懂了，剩下的就是这三种的变种了，换汤不换药？
1. 01 背包问题
01背包问题链接
0 1 背包问题就是说每一件物品只能选择一次，所以我们每次选择的时候，只用两种可能，选或不选，0和1也就此而来。
1.二维解决
- 状态表示:
- 集合:
f[i][j]代表前i件物品中体积不超过j的所有价值 - 属性: 将所有的价值取
max - 状态计算:
- 对于当前的这一状态
f[i][j]可以由上一个状态转移过来: - 0 - 不选选择当前物品
f[i][j] = f[i - 1][j]. - 1 - 选择当前物品
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])
不选当前物品好理解，就是去直接继承选到前一个物品时候的价值.
而选择当前物品是有条件的，就是说当前背包的容量j 必须大于等于当前的物品的体积v[i]才能选择.j - v[i]说的是当前背包的容量减去当前物品的体积，咱既然要选择这个物品，那么必须得这个物品留出相应的空间。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N]; //v体积，w价值
int f[N][N]; //f[i][j] 表示前i件物品中体积是j的最大价值.
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d", &v[i], &w[i]);
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
{
f[i][j] = f[i - 1][j];
if (j >= v[i])
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
printf("%d\n", f[n][m]);
return 0;
}
2. 一维优化
我们还可以对其进行进行优化，可以讲二维优化成一维。
f[i]表示体积是i时候的最大价值.
f[i][j] = f[i - 1][j]变成f[j] = f[j]所以可以直接不写f[i - 1][j - v[i]]变成f[j - v[i]]但是此变形并不是等价的，因为我们在真正循环的过程中其实是用f[i][j - v[i]]于前面的不符，需要将其进行逆序。
大家也可看看这这一篇题解
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N]; //v体积，w价值
int f[N]; //f[i][j] 表示前i件物品中体积是j的最大价值.
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d", &v[i], &w[i]);
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
printf("%d\n", f[m]);
return 0;
}
2. 完全背包问题
完全背包问题链接
完全背包问题和01背包问题唯一的区别就是，完全背包中的物品可以使用无限次，
而01背包中的物品只能使用一次。
1.暴力3 for.
- 状态表示:
- 集合:
f[i][j]表示背包容量是i中所选体积不超过j的所有价值 - 属性: 对所有的价值取
max - 状态计算:
- 因为每一个物品可以选择无限次,前提是满足背包容量.
我们尝试用一个变量 k 来充当第i个物品选取k次，
那么k的范围则是 [0,k] 但是k必须满足 k * v[i] <= j.
因为选取的体积不能超过背包的总容量。
即： f[i][j] = max(f[i][j],f[i - 1][j - k * v[i]] + k * w[i]);
- 可以发现上面的方程和01背包问题一摸一样，只是多了一个
k而已。如果不理解，将k = 1代入即使01背包问题的动态转移方程。而不选的时候则k = 0.
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d", &v[i], &w[i]);
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
for (int k = 0; k * v[i] <= j; k++)
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
printf("%d\n", f[n][m]);
return 0;
}
这道题目用这个代码是会超时的，但是思路肯定是对的，理解思路才能理解下面的优化。
2. 二维优化
我们将上述的动态转移方程展开
2v = 2 * v && 2w = 2 * w;
f[i][j] = max(f[i-1][j-0v],f[i-1][j-v]+w,f[i-1][j-2v]+2w,f[i - 1][3v]+3w,...)
f[i][j-v] = max(f[i-1][j-v-0v]+0w,f[i-1][j-v-v]+w,f[i-1][j-2v]+2w+....)
我们可以发现，f[i][j]展开的这一大堆于f[i][j - v]展开的这一大堆是仅仅相差一个w。
所以:
f[i][j] = max(f[i - 1][j], f[i][j - v] + w).
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d", &v[i], &w[i]);
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
{
f[i][j] = f[i - 1][j];
if (j >= v[i])
f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}
printf("%d\n", f[n][m]);
return 0;
}
这个代码于01背包问题二维进仅仅差1个数字.
3. 一维优化
既然只差那一个数字，所以完全背包也可以将其进行优化成一维的。
我们之间在优化01背包的时候提到过：
f[i][j] = f[i- 1][j]转化成f[j] = f[j]直接可以省略掉。- 而01背包因为
f[i - 1][j - v[i]]转化成f[j]因为是i - 1所以需要逆序体积遍历。 - 在完全背包中
f[i][j - v[i]]转化成f[j]因为是i所以不需要进行逆序。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d", &v[i], &w[i]);
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <= m; j++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
printf("%d\n", f[m]);
return 0;
}
3. 多重背包问题Ⅰ.
多重背包问题Ⅰ链接
多重背包问题是将物品的个数做了限制，在给定的这些物品中，选择总价值不超过所给背包体积的最大总价值。
1. 二维解决
我们在上面的完全背包问题中已经学会了0~k次的选择一个物品，至于k的范围则是使k * v[i] <= j将其最大化。而本题中则可以直接获取。
前两种背包问题真的搞懂之后，这道题只需要加一个条件即可。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int f[N][N];
int v[N], w[N], cnt[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d%d", &v[i], &w[i], &cnt[i]);
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
for (int k = 0; k <= cnt[i] && k * v[i] <= j; k++)
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
printf("%d\n", f[n][m]);
return 0;
}
2. 一维优化
同之前的优化一样，直接去掉一个维度。
他是01背包问题的变种，删除前是i - 1与删除后并不是等价的，所以需要逆序。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int f[N];
int v[N], w[N], cnt[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d%d", &v[i], &w[i], &cnt[i]);
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
for (int k = 0; k <= cnt[i] && k * v[i] <= j; k++)
f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
printf("%d\n", f[m]);
return 0;
}
4. 多重背包问题Ⅱ
多重背包问题Ⅱ链接
这个问题与上方的区别只是数据范围变了，之所以单独拿出来，是因为，这里涉及到了一个二进制的优化，感觉还是挺重要的。
我们假设去店里面送水果，有13颗苹果，16颗梨，11颗西瓜。需要讲这40个水果搬如店中，我们如果一个一个搬，需要40次，说实话有点捞。。。但凡是个正常人我们都应该讲其分开搬，具体怎么分呢，我们采取二进制的方式将其分开。
1,2,4,8,16,32........等等这样一直分下去，但前提一定得是一样的物品分一起，不然你的体积和价值如何计算？
上述例子：
苹果: 1, 2 ,4, 7.
梨: 1, 2, 4, 8, 1.
西瓜: 1, 2, 4, 4.
我只是举个例子，现实生活中肯定不是二进制的搬，1个苹果占一个箱子？
下面的代码就是向上述例子一样，将其一类一类的分组打包。
然后就会变成了01背包问题。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = 2010;
int n, m;
int v[N], w[N];
int f[M];
int main()
{
scanf("%d%d", &n, &m);
int cnt = 0; //从1开始放。
for (int i = 1; i <= n; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
int k = 1;
while (k <= c)
{
v[++cnt] = a * k; //先++。
w[cnt] = b * k;
c -= k;
k *= 2;
}
if (c > 0)
{
v[++cnt] = a * c;
w[cnt] = b * c;
}
}
n = cnt;
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
printf("%d\n", f[m]);
return 0;
}
5. 混合背包问题
混合背包问题链接
混合背包问题就是讲前面所说的3中背包混合在一起。
我们既然已经会了前三种的状态转移方程，那么我们只需要在做的时候，对其进行套用相应的方程即可。
又因为多重背包问题可以将其进行二进制优化转化为01背包问题，所以我们只需要对其进行2个方程各自对应即可。
总的来说也就2个步骤
- 将多重背包利用二进制优化转化为01背包
- 将01背包与完全背包各自动态转移方程代入即可。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1010;
int n, m;
int f[N];
struct Thing
{
int kind;
int v, w;
};
vector<Thing> things;
int main()
{
scanf("%d%d", &n, &m);
//第一步:将多重背包利用二进制优化转化为01背包
for (int i = 1; i <= n; i++)
{
int v, w, s;
scanf("%d%d%d", &v, &w, &s);
if (s <= 0) //01背包或者完全背包直接插入即可。
things.push_back({s, v, w});
else
{
//多重背包进行二进制优化，分包
for (int k = 1; k <= s; k *= 2)
{
s -= k;
things.push_back({-1, v * k, w * k});
}
if (s > 0)
things.push_back({-1, v * s, w * s});
}
}
//第二步:将01背包与完全背包各自动态转移方程代入即可。
for (auto t : things)
{
if (t.kind == -1) //01背包的动态转移方程
for (int j = m; j >= t.v; j--)
f[j] = max(f[j], f[j - t.v] + t.w);
else //完全背包的动态转移方程
for (int j = t.v; j <= m; j++)
f[j] = max(f[j], f[j - t.v] + t.w);
}
printf("%d\n", f[m]);
return 0;
}
6. 二维费用背包问题
二维费用背包问题链接
二维费用，只是多了一个书包的承受范围，只需要在01背包的基础上多加一层关于重量的的循环就好了。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, V, M; //个数，容积， 承受范围
int v[N], m[N], w[N]; //体积，重量，价值
int f[N][N]; //f[i][j]表示容积不超过i，重量不超过j的最大价值
int main()
{
scanf("%d%d%d", &n, &V, &M);
for (int i = 1; i <= n; i++)
scanf("%d%d%d", &v[i], &m[i], &w[i]);
for (int i = 1; i <= n; i++)
for (int j = V; j >= v[i]; j--) //容积
for (int k = M; k >= m[i]; k--) //承受范围
f[j][k] = max(f[j][k], f[j - v[i]][k - m[i]] + w[i]);
printf("%d\n", f[V][M]);
return 0;
}
7. 分组背包问题
分组背包问题链接
分组背包问题，其实归根结底还是01背包问题，每组只能选择一个物品出来，只不过这一组有很多个物品。
所以我们针对其每一组，将其所有的物品都遍历一遍就好了，在01背包问题上再加一层循环，3for就好了。
01背包问题，同样还是逆序，不过判断j >= v[i]的条件变成了j >= v[k]了。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int f[N], v[N], w[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
int s;
scanf("%d", &s);
for (int j = 1; j <= s; j++)
scanf("%d%d", &v[j], &w[j]);
for (int j = m; j >= 0; j--)
for (int k = 1; k <= s; k++)
if (j >= v[k])
f[j] = max(f[j], f[j - v[k]] + w[k]);
}
printf("%d\n", f[m]);
return 0;
}
🎈🎈🎈🎈🎈🎈🎈🎈🎈🎈🎈🎈🎈🎈
