更好的阅读体验

背包问题是DP动态规划算法中比较经典的一类模型,在NOIP考场上不定期地上位,令人琢磨不透,但是一旦学会了他,你就可以在短短十分钟的时间里,切掉他,达到节约时间,而且一次AC的目的.——某位大佬

以上就是本次的思维导图,即学习框架.
首先我们以01背包,所有背包的基础,开始进行本次的学习!

01背包

题目链接
有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，$N，V$，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
$0 \lt N, V \le 1000$
$0\lt v_i, w_i \le 1000$

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

朴素思路

首先这道题目很明显的思路就是,对于一个物品而言,我们只有两种选择.

1. 可以选择将他放入背包
2. 不选择他,不放入背包中.
   那么一个朴素思路就是,我们可以使用二进制枚举,枚举每一个物品,我们到底是,选择这个物品,还是不选择这个物品.
   时间复杂度$O(2^N)$

DP思想 $O(n \times m)$

对于上面所说的复杂度,我们显然是不满意的,那么既然如此的话,我们如何去优化他呢?我们会想到动态规划(DP),因为这道题目有几个特殊的地方:

1. 我们选择第i件物品,对于后面的物品并没有任何影响,即无后效.
2. 它的决策非常明显,也就是我们只有,选择这个物品 或者 不选择这个物品这两种方案.

综上所述,我们可以先考虑考虑DP算法.
那么现在我们就要开始动态规划算法的思考题目流程.

1. 状态数组如何定义
2. 阶段是什么
3. 决策是什么
4. 边界是什么
5. 状态转移方程

状态数组的定义

状态数组的定义:往往就是题目要我们求解的最终答案,所以我们大致可以这么定义状态数组.
对于$f[i][j]$,它表示为,在前i个物品选取若干个,已经花费的容量为j的最大利润.
举个例子,$f[3][5]$表示为在前三个物品中,我们选取0或者1或者2或者3个,然后已经花费了5点容量的最大利润.
如果觉得例子解释不好,可以不看,害怕误解

阶段

根据我们的状态数组,我们可以这么选择阶段,也就是$1 \le i \le n$,就是以物品为阶段.

决策

决策很明显,就是选取或者不选选取

边界条件

f数组全部清空就好了,因为我们要求的是最大利润.

状态转移方程

f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i];

$f[i-1][j]$就是前i-1个物品,花费j个容量的最大利润,在这里我们可以理解为,不选取第i个物品(即选取前i-1个)的最大利润.
$f[i][j-v[i]]+w[i]$就是选取第i个物品,花费为j个容量的最大利润,那么为什么要这么写?
因为我们要放入这个物品,那么至少我们得需要$v[i]$个容量,所以我们只能从$j-v[i]$这个容量推过来,不然我们放不下这个背包.
$+w[i]$很明显就是选取了这个物品,当然要将这个物品的价值加上去.

滚动数组优化

第一步优化:
首先,对于状态数组而言,我们只利用了$f[i][j]$和$f[i-1][j]$.如下面这个例子所示

1. 当i为1的时候,我们利用的是$f[0][j]$和$f[1][j]$
2. 当i为2的时候,我们利用的是$f[1][j]$和$f[2][j]$
3. 当i为3的时候,我们利用的是$f[2][j]$和$f[3][j]$

所以其实我们只需要利用$f[0][j]$和$f[1][j]$就好了,0实际上表示i-1,1实际上表示i.
第二步优化:
实际上我们的j不一定要从$v[i],1+v[i],2+v[i]…m$,而是可以从$m,m-1.m-2…v[i]$因为这样的话,我们就可以从$f[2][n]$到$f[n]$了.因为刚开始没有处理第二种决策的时候,$f[1][j]$肯定等于$f[0][j]$,然后我们从m到$v[i]$,开始从上到下开始决策,就可以忽略$f[0]$这一维了.
这里讲的不太好,建议还是自行模拟一遍吧=￣ω￣=

具体代码实现

#include <bits/stdc++.h>
using namespace std;
const int N=1100;
const int M=2e5;
int n,m,i,j,k,a[N],f[M];
int main()
{
    ios::sync_with_stdio(false);
    cin>>m>>n;//读入最大容量和物品个数
    for(int i=1;i<=n;i++)
        cin>>a[i]; 
    memset(f,0xcf,sizeof(f));//我这里是初始化为-INF,其实初始化为0就好了.
    f[0]=0;
    for(int i=1;i<=n;i++)//选取i个物品
        for(int j=m;j>=a[i];j--)//容量设定
            f[j]=max(f[j],f[j-a[i]]+a[i]);//转移
    int ans=0;
    for(int i=0;i<=m;i++)//f[n][i]表示选取n个物品,消耗容量为i的最有价值.
        ans=max(ans,f[i]);
    cout<<ans;//最优解
    return 0;
}