蓝桥杯备考背包初次了解以及01背包
目录
蓝桥杯备考：背包初次了解以及01背包
背包就是说给一个有容量的背包，比如说给一个总体积V，给一堆物品 每个物品都有对应的体积
每个物品都有对应的闪光值，我们要让这个闪光值最大，但是不能超过总体积，
背包问题有多种变体
01背包表示每个物品要么被选要么不被选
完全背包表示每个物品可以被选多次
分组背包表示把物品分组，每个组只能选一个
多重背包表示每个物品都是有数量的
问法除了有求最大的闪光度，也可以是求方案总数，也可以是求方案可行性或者输出具体的方案
这是一道很经典的01背包模板题，我们先做一下第一小问
我们还是老样子，按顺序来分析
step1:确定状态表示 我们用一维的化就是表示f[i]是从1到i个物品里选出最大价值，但是我们的限制条件是有两个的呀？我们不能就这么用一个一维的dp数组解决它，我们应该开个二维的
f[i][j]表示的是 从1到i个物品里选出体积不超过j的最大价值
step2:确认状态转移方程
当然，这里我们一定要注意的是，如果要选a[i]这个物品的话呢，前提是j必须大于等于a[i]
step3: 初始化
step4:确定填表顺序，应该是从上到下的
好的，话不多说，我们来实现一下我们的代码
#include <iostream>
using namespace std;
const int N = 1e4+10;
int v[N],w[N];
int n,m;
int f[N][N];
int main()
{
cin >> n >> m;
for(int i = 1;i<=n;i++)
{
cin >> v[i] >> w[i];
}
for(int i =1;i<=n;i++)
{
for(int j = 1;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]);
}
}
}
cout << f[n][m] << endl;
return 0;
}除此之外，我们还需要再分析一下第二问
step1:f[i][j]表示从1到i个物品里选出体积刚好为j的价值最大的物品
step2:确定状态转移方程，实际上和第一问是一样的
step3:初始化：这里就开始出现差别了，我们恰好的话呢
肯定是有些格子不能存值的，因为体积加起来不可能刚好满足所有下标，最显而易见的就是图上第一行f[0][1~4]选0个物品恰好体积是1到4，这个是一定不可能的，我们可以把它设置为负无穷，然后取max的时候是不影响的，特殊的f[0][0]是可以填0的，因为选0个物品总价值刚好为0是可以的
step4 从上到下填表
实现代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3+10;
int v[N],w[N];
int n,m;
int f[N][N];
int main()
{
memset(f,-0x3f,sizeof f);
f[0][0] = 0;
cin >> n >> m;
for(int i = 1;i<=n;i++)
{
cin >> v[i] >> w[i];
}
for(int j = 0;j<=n;j++)
{
f[j][0] = 0;
}
for(int i =1;i<=n;i++)
{
for(int j = 1;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]);
}
}
}
if(f[n][m] < 0) cout << 0 << endl;
else cout << f[n][m] << endl;
return 0;
}