蓝桥杯备考：背包初次了解以及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;
}