背包dp
导入：
动态规划，与贪心算法不同，能用贪心算法解决的问题具有所谓的‘最优子’的结构，也就是能够从‘局部最优解’导出最终答案。而动态规划问题一般不具有这种结构，这个时候就可以想办法将原来的问题分解成一堆子问题，通过所有子问题的局部最优解导出最终的答案，其中最具典型的便是‘背包问题’。
#1.01背包问题
[NOIP2005 普及组] 采药
题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有 2 个整数 T（1 \le T \le 1000）和 $M$（1 \le M \le 100），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。
接下来的 M行每行包括两个在 1到 100之间（包括 1 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
样例 #1
样例输入 #1
70 3
71 100
69 1
1 2样例输出 #1
3提示
【数据范围】
- 对于 30% 的数据，M \le 10；
- 对于全部的数据，M \le 100。
【题目来源】
NOIP 2005 普及组第三题
我们可以发现，这类问题并不满足贪心算法所谓的最优子结构，这类问题需要采用动态规划来解题。
01背包问题只有取与不取两种状态，对应二进制的0和1，与此对应的该题目。
下面给出题解：
二维数组版本：
#include<iostream>
using namespace std;
const int N = 1010,M = 110;
int dp[N][M],tim[M],val[M];
int main(){
int n,m;
cin >> n >> m ;
for (int i = 1 ; i <= m; i++){
cin >> tim[i] >> val[i];
}
for (int i = 1 ; i <= m; i++){
for (int l = n ; l >= 0 ; l--){
if(l >= tim[i]){
dp[i][l] = max(dp[i-1][l],dp[i-1][l-tim[i]]+val[i]);
}
else{
dp[i][l] = dp[i-1][l];
}
}
}
printf("%d",dp[m][n]);
return 0;
}一维数组版本：
#include<bits/stdc++.h>
using namespace std;
int tim[110],val[110],fn[1100];
int main(){
int M,n;
scanf("%d%d",&M,&n);
for(int i = 1; i <= n; i++) {
scanf("%d%d",&tim[i],&val[i]);
}
for(int i = 1; i <= n; i++) {
for(int l = M; l >= tim[i]; l--) {
if(fn[l-tim[i]] + val[i] > fn[l]) fn[l] = fn[l-tim[i]] + val[i];
}
}
printf("%d",fn[M]);
return 0;
}这种方法的具体思路是，将最大时间以内的所有时间状态作为下标设置为一个数组，这种数组一般被命名为dp(我这里用了fn来代替)，输入了所有的(时间，价值)样例并且将其保存在对应的数组之后，通过构造两层的for循环得到答案，而问题的核心就在这个for循坏里，也就是那个’状态转移方程’。
我们可以通过测试输出来理解这种问题的原理:
30 4
31 12
20 5
10 4
6 6
l = 30 tim[1] = 31 fn[l] = 0
l = 29 tim[1] = 31 fn[l] = 0
l = 28 tim[1] = 31 fn[l] = 0
l = 27 tim[1] = 31 fn[l] = 0
l = 26 tim[1] = 31 fn[l] = 0
l = 25 tim[1] = 31 fn[l] = 0
l = 24 tim[1] = 31 fn[l] = 0
l = 23 tim[1] = 31 fn[l] = 0
l = 22 tim[1] = 31 fn[l] = 0
l = 21 tim[1] = 31 fn[l] = 0
l = 20 tim[1] = 31 fn[l] = 0
l = 19 tim[1] = 31 fn[l] = 0
l = 18 tim[1] = 31 fn[l] = 0
l = 17 tim[1] = 31 fn[l] = 0
l = 16 tim[1] = 31 fn[l] = 0
l = 15 tim[1] = 31 fn[l] = 0
l = 14 tim[1] = 31 fn[l] = 0
l = 13 tim[1] = 31 fn[l] = 0
l = 12 tim[1] = 31 fn[l] = 0
l = 11 tim[1] = 31 fn[l] = 0
l = 10 tim[1] = 31 fn[l] = 0
l = 9 tim[1] = 31 fn[l] = 0
l = 8 tim[1] = 31 fn[l] = 0
l = 7 tim[1] = 31 fn[l] = 0
l = 6 tim[1] = 31 fn[l] = 0
l = 5 tim[1] = 31 fn[l] = 0
l = 4 tim[1] = 31 fn[l] = 0
l = 3 tim[1] = 31 fn[l] = 0
l = 2 tim[1] = 31 fn[l] = 0
l = 1 tim[1] = 31 fn[l] = 0
l = 0 tim[1] = 31 fn[l] = 0
l = 30 tim[2] = 20 fn[l] = 5
l = 29 tim[2] = 20 fn[l] = 5
l = 28 tim[2] = 20 fn[l] = 5
l = 27 tim[2] = 20 fn[l] = 5
l = 26 tim[2] = 20 fn[l] = 5
l = 25 tim[2] = 20 fn[l] = 5
l = 24 tim[2] = 20 fn[l] = 5
l = 23 tim[2] = 20 fn[l] = 5
l = 22 tim[2] = 20 fn[l] = 5
l = 21 tim[2] = 20 fn[l] = 5
l = 20 tim[2] = 20 fn[l] = 5
l = 19 tim[2] = 20 fn[l] = 0
l = 18 tim[2] = 20 fn[l] = 0
l = 17 tim[2] = 20 fn[l] = 0
l = 16 tim[2] = 20 fn[l] = 0
l = 15 tim[2] = 20 fn[l] = 0
l = 14 tim[2] = 20 fn[l] = 0
l = 13 tim[2] = 20 fn[l] = 0
l = 12 tim[2] = 20 fn[l] = 0
l = 11 tim[2] = 20 fn[l] = 0
l = 10 tim[2] = 20 fn[l] = 0
l = 9 tim[2] = 20 fn[l] = 0
l = 8 tim[2] = 20 fn[l] = 0
l = 7 tim[2] = 20 fn[l] = 0
l = 6 tim[2] = 20 fn[l] = 0
l = 5 tim[2] = 20 fn[l] = 0
l = 4 tim[2] = 20 fn[l] = 0
l = 3 tim[2] = 20 fn[l] = 0
l = 2 tim[2] = 20 fn[l] = 0
l = 1 tim[2] = 20 fn[l] = 0
l = 0 tim[2] = 20 fn[l] = 0
l = 30 tim[3] = 10 fn[l] = 9
l = 29 tim[3] = 10 fn[l] = 5
l = 28 tim[3] = 10 fn[l] = 5
l = 27 tim[3] = 10 fn[l] = 5
l = 26 tim[3] = 10 fn[l] = 5
l = 25 tim[3] = 10 fn[l] = 5
l = 24 tim[3] = 10 fn[l] = 5
l = 23 tim[3] = 10 fn[l] = 5
l = 22 tim[3] = 10 fn[l] = 5
l = 21 tim[3] = 10 fn[l] = 5
l = 20 tim[3] = 10 fn[l] = 5
l = 19 tim[3] = 10 fn[l] = 4
l = 18 tim[3] = 10 fn[l] = 4
l = 17 tim[3] = 10 fn[l] = 4
l = 16 tim[3] = 10 fn[l] = 4
l = 15 tim[3] = 10 fn[l] = 4
l = 14 tim[3] = 10 fn[l] = 4
l = 13 tim[3] = 10 fn[l] = 4
l = 12 tim[3] = 10 fn[l] = 4
l = 11 tim[3] = 10 fn[l] = 4
l = 10 tim[3] = 10 fn[l] = 4
l = 9 tim[3] = 10 fn[l] = 0
l = 8 tim[3] = 10 fn[l] = 0
l = 7 tim[3] = 10 fn[l] = 0
l = 6 tim[3] = 10 fn[l] = 0
l = 5 tim[3] = 10 fn[l] = 0
l = 4 tim[3] = 10 fn[l] = 0
l = 3 tim[3] = 10 fn[l] = 0
l = 2 tim[3] = 10 fn[l] = 0
l = 1 tim[3] = 10 fn[l] = 0
l = 0 tim[3] = 10 fn[l] = 0
l = 30 tim[4] = 6 fn[l] = 11
l = 29 tim[4] = 6 fn[l] = 11
l = 28 tim[4] = 6 fn[l] = 11
l = 27 tim[4] = 6 fn[l] = 11
l = 26 tim[4] = 6 fn[l] = 11
l = 25 tim[4] = 6 fn[l] = 10
l = 24 tim[4] = 6 fn[l] = 10
l = 23 tim[4] = 6 fn[l] = 10
l = 22 tim[4] = 6 fn[l] = 10
l = 21 tim[4] = 6 fn[l] = 10
l = 20 tim[4] = 6 fn[l] = 10
l = 19 tim[4] = 6 fn[l] = 10
l = 18 tim[4] = 6 fn[l] = 10
l = 17 tim[4] = 6 fn[l] = 10
l = 16 tim[4] = 6 fn[l] = 10
l = 15 tim[4] = 6 fn[l] = 6
l = 14 tim[4] = 6 fn[l] = 6
l = 13 tim[4] = 6 fn[l] = 6
l = 12 tim[4] = 6 fn[l] = 6
l = 11 tim[4] = 6 fn[l] = 6
l = 10 tim[4] = 6 fn[l] = 6
l = 9 tim[4] = 6 fn[l] = 6
l = 8 tim[4] = 6 fn[l] = 6
l = 7 tim[4] = 6 fn[l] = 6
l = 6 tim[4] = 6 fn[l] = 6
l = 5 tim[4] = 6 fn[l] = 0
l = 4 tim[4] = 6 fn[l] = 0
l = 3 tim[4] = 6 fn[l] = 0
l = 2 tim[4] = 6 fn[l] = 0
l = 1 tim[4] = 6 fn[l] = 0
l = 0 tim[4] = 6 fn[l] = 0
11
可以看到tim【1】被跳过了，因为这个数字大于了最大时间
tim【2】被执行了十一次，将背包(时间)在状态30到20时的所能采集到的药材价值val【2】赋值给fn【30】,fn【29】…fn【20】，之后由于状态时间(l)小于了tim【2】(第2个药材所需要采集的时间)，于是跳过
之后来到tim【3】，对于fn的每一个fn【l】，且l大于tim【3】(第三个药材的采集时间)，将其与fn【l - tim【i】】 + val【i】进行比较，取最值。也就是说，将与时间状态l差值为tim【3】(第三个药材采集时间的)的时间状态的价值加上val【l】(第三个药材的价值)与原来的时间状态l下的价值进行比较，如果可以取到更大的值，说明该选择更优，便进行状态的更新。
不必纠结为什么取30(最大时间)，即使在价值最大时填不满所有的时间(比如说价值最大时事实上只要花费26单位的时间，最大值进行的状态更新，是对应的26单位的最优解的，从输出测试也可以看出，因为背包dp的关键是要从后往前遍历)
小书童——刷题大军
题目背景
数学是火，点亮物理的灯；物理是灯，照亮化学的路；化学是路，通向生物的坑；生物是坑，埋葬学理的人。 文言是火，点亮历史宫灯；历史是灯，照亮社会之路；社会是路，通向哲学大坑；哲学是坑，埋葬文科生。——小A
题目描述
小A“刷题”十分猖狂，明目张胆地“刷题”。他现在在小书童里发现了n样他喜欢的“题目”，每“题”都有他的需要时间，而老师布置了m项作业，每项作业都有它的需要时间及分值，老师规定k分以上算及格。小A只剩r个单位时间，他想在及格的基础上更多地“刷题”。
输入格式
第一行：n m k r。第二行：n个数，代表每“题”他的需要时间。第三行：m个数。表示每项作业它的需要时间。第四行：m个数。代表每项作业它的分值。
输出格式
一个数，代表小A能刷几道题
样例 #1
样例输入 #1
3 4 20 100
15 20 50
10 15 40 40
5 5 10 15样例输出 #1
2提示
没有不能及格的情况
对于100%的数据，n\le 10,m\le 10,k\le 50,r\le 150
###以上为01背包的变式问题，01背包问题的关键是取与不取两种状态，对应二进制的0和1
以下是提供参考的源代码：
#include<bits/stdc++.h>
using namespace std;
int sat[11];
int til[152] = {0};
struct homework{
int score;
int time;
}wok[11];
int main(){
int n,m,k,r;
scanf("%d%d%d%d",&n,&m,&k,&r);//satisfiying,all,scorelimit,timelimit
for(int i = 1; i <= n; i++){
cin >> sat[i];
}
sort(sat+1, sat+1+n, less<int>());
for(int i = 1; i <= m; i++){
cin >> wok[i].time;
}
for(int i = 1; i <= m; i++){
cin >> wok[i].score;
}
for(int i = 1; i <= m; i++){
for(int l = r; l >= wok[i].time; l--){
int tmp = wok[i].score + til[l-wok[i].time];
til[l] = max(tmp,til[l]);
//cout << "til[" << l << "] = " << til[l] << endl;
}
}
int idx;
for(int i = 1; i <= r; i++)
if(til[i] >= k){
//cout << i << endl;
idx = r - i;
break;
}
//cout << "you idiot!" << endl;
int ans = 0;
for(int i = 1; i <= n; i++){
idx -= sat[i];
if(idx < 0) break;
ans++;
}
printf("%d",ans);
}首先确定究竟是什么东西需要进行状态转移，本题具有较强的迷惑性，究竟是分数作为状态，还是时间作为状态？
稍作思考就可以发现，我们需要的是小书童可以获得尽可能多的时间进行刷题，但是这又有及格条件的限制，于是我们可以想到使用贪心的策略来使小书童获得尽可能多的时间。
而当我们获得了足够的时间之后，我们发现这又变成了一个背包dp的问题，我们可以发现状态转移方程甚至与之前那题没有什么区别。。。
综上所述，01背包问题的关键是：
确定状态，一般来说含有子集关系的事物可以作为状态，比如背包容量与物品所占的背包容量，一般答案作为容量对应下的值。
确定状态转移方程。
也可以看出01背包只是标准的模板题。。。
之后便是
#2.完全背包问题
疯狂的采药
题目背景
此题为纪念 LiYuxiang 而生。
题目描述
LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是 LiYuxiang，你能完成这个任务吗？
此题和原题的不同点：
$1$. 每种草药可以无限制地疯狂采摘。
$2$. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！
输入格式
输入第一行有两个整数，分别代表总共能够用来采药的时间 $t$ 和代表山洞里的草药的数目 $m$。
第 $2$ 到第 $(m + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数 $a_i, b_i$ 分别表示采摘第 $i$ 种草药的时间和该草药的价值。
输出格式
输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例 #1
样例输入 #1
70 3
71 100
69 1
1 2样例输出 #1
140提示
数据规模与约定
- 对于 $30%$ 的数据，保证 $m \le 10^3$ 。
- 对于 $100%$ 的数据，保证 $1 \leq m \le 10^4$，$1 \leq t \leq 10^7$，且 $1 \leq m \times t \leq 10^7$，$1 \leq a_i, b_i \leq 10^4$。
下面给出题解：
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
const int N = 1e4+10;
const int M = 1e7+10;
ll tim[N],val[N],dp[M];
int main(){
int t,m;
scanf("%d%d",&t,&m);
for(int i = 1; i <= m ; i++){
scanf("%lld%lld",&tim[i],&val[i]);
}
for(int i = 1; i <= m; i++){
for(int j = tim[i]; j <= t; j++){
dp[j] = max(dp[j], dp[j-tim[i]]+val[i]);
//printf("%d %d %d\n",i,tim[i],dp[j]);
}
for(int k = 1; k <= t; k++){
//printf("i = %d dp[%d] = %d\n",i,k,dp[k]);
}
}
printf("%lld",dp[t]);
}同样地，给出测试样例：
30 4
25 3
6 2
11 5
12 7
i = 1 dp[1] = 0
i = 1 dp[2] = 0
i = 1 dp[3] = 0
i = 1 dp[4] = 0
i = 1 dp[5] = 0
i = 1 dp[6] = 0
i = 1 dp[7] = 0
i = 1 dp[8] = 0
i = 1 dp[9] = 0
i = 1 dp[10] = 0
i = 1 dp[11] = 0
i = 1 dp[12] = 0
i = 1 dp[13] = 0
i = 1 dp[14] = 0
i = 1 dp[15] = 0
i = 1 dp[16] = 0
i = 1 dp[17] = 0
i = 1 dp[18] = 0
i = 1 dp[19] = 0
i = 1 dp[20] = 0
i = 1 dp[21] = 0
i = 1 dp[22] = 0
i = 1 dp[23] = 0
i = 1 dp[24] = 0
i = 1 dp[25] = 3
i = 1 dp[26] = 3
i = 1 dp[27] = 3
i = 1 dp[28] = 3
i = 1 dp[29] = 3
i = 1 dp[30] = 3
i = 2 dp[1] = 0
i = 2 dp[2] = 0
i = 2 dp[3] = 0
i = 2 dp[4] = 0
i = 2 dp[5] = 0
i = 2 dp[6] = 2
i = 2 dp[7] = 2
i = 2 dp[8] = 2
i = 2 dp[9] = 2
i = 2 dp[10] = 2
i = 2 dp[11] = 2
i = 2 dp[12] = 4
i = 2 dp[13] = 4
i = 2 dp[14] = 4
i = 2 dp[15] = 4
i = 2 dp[16] = 4
i = 2 dp[17] = 4
i = 2 dp[18] = 6
i = 2 dp[19] = 6
i = 2 dp[20] = 6
i = 2 dp[21] = 6
i = 2 dp[22] = 6
i = 2 dp[23] = 6
i = 2 dp[24] = 8
i = 2 dp[25] = 8
i = 2 dp[26] = 8
i = 2 dp[27] = 8
i = 2 dp[28] = 8
i = 2 dp[29] = 8
i = 2 dp[30] = 10
i = 3 dp[1] = 0
i = 3 dp[2] = 0
i = 3 dp[3] = 0
i = 3 dp[4] = 0
i = 3 dp[5] = 0
i = 3 dp[6] = 2
i = 3 dp[7] = 2
i = 3 dp[8] = 2
i = 3 dp[9] = 2
i = 3 dp[10] = 2
i = 3 dp[11] = 5
i = 3 dp[12] = 5
i = 3 dp[13] = 5
i = 3 dp[14] = 5
i = 3 dp[15] = 5
i = 3 dp[16] = 5
i = 3 dp[17] = 7
i = 3 dp[18] = 7
i = 3 dp[19] = 7
i = 3 dp[20] = 7
i = 3 dp[21] = 7
i = 3 dp[22] = 10
i = 3 dp[23] = 10
i = 3 dp[24] = 10
i = 3 dp[25] = 10
i = 3 dp[26] = 10
i = 3 dp[27] = 10
i = 3 dp[28] = 12
i = 3 dp[29] = 12
i = 3 dp[30] = 12
i = 4 dp[1] = 0
i = 4 dp[2] = 0
i = 4 dp[3] = 0
i = 4 dp[4] = 0
i = 4 dp[5] = 0
i = 4 dp[6] = 2
i = 4 dp[7] = 2
i = 4 dp[8] = 2
i = 4 dp[9] = 2
i = 4 dp[10] = 2
i = 4 dp[11] = 5
i = 4 dp[12] = 7
i = 4 dp[13] = 7
i = 4 dp[14] = 7
i = 4 dp[15] = 7
i = 4 dp[16] = 7
i = 4 dp[17] = 7
i = 4 dp[18] = 9
i = 4 dp[19] = 9
i = 4 dp[20] = 9
i = 4 dp[21] = 9
i = 4 dp[22] = 10
i = 4 dp[23] = 12
i = 4 dp[24] = 14
i = 4 dp[25] = 14
i = 4 dp[26] = 14
i = 4 dp[27] = 14
i = 4 dp[28] = 14
i = 4 dp[29] = 14
i = 4 dp[30] = 16
16
注意这道题目的数据类型比较大，需要开long long不然会有样例过不了。
完全背包问题与01背包问题的区别在于：01背包只有取与不取两种状态，而完全背包则是【取多少】的问题。
我们可以发现完全背包问题的状态转移方程几乎与01背包问题的几乎一模一样，只是遍历的顺序从逆序变成了顺序。为什么会这样？
这仍然是一个dp问题，他的实现方式是不断地顺序遍历，第一层循环我们可以看出状态25以及以上被3填满了(为了方便我自己的理解(bushi)，时间状态这里我说成背包容量)这与01背包好像没有什么区别，而到了第二层循环如果仍然是01背包(逆序)的方法的话，我们可以发现这时候的状态序列应该是00000222……222333333，也就是当假设背包最大容量为25以下时候，最优解是取一个价值为【2】的草药，25及其以上则是【3】的草药。而如果使用完全背包的方法，它就会不可避免地在顺序遍历的过程中向后检测到已经遍历过的元素(dp[j-tim[i]]+val[i])，这个已经遍历过的元素可能已经被更新了(也就是取了当前物品一次，更新依据是当前最大容量状态的价值是否小于取了一次后在该最大容量状态的价值)，但是如果更优我们还是可以在这个基础上取，一直到真正的最大容量为止。这就是无限次数取的意义。。。
