01背包
动态规划是一种高效的算法。在数学和计算机科学中，是一种将复杂问题的分成多个简单的小问题思想 ---- 分而治之。因此我们使用动态规划的时候，原问题必须是重叠的子问题。运用动态规划设计的算法比一般朴素算法高效很多，因为动态规划不会重复计算已经计算过的子问题。因为动态规划又可以称为“记忆化搜索”。
01背包是介绍动态规划最经典的例子，同时也是最简单的一个。我们先看看01背包的是什么？
问题(01背包)：
有n个重量和价值分别为vi和ci的物品。从这些物品中挑出总重量不超过m的物品，求所有挑选方案中价值总和的最大值。
这就是被称为01背包的问题。在没学习动态规划之前，我们看到这个问题第一反应会用dfs搜索一遍。那我们先使用这种方法来求解01背包问题：
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e3+;
int n,m,v[N],c[N];
//从第i个物品开始挑选总重量不大于sumv的部分
int dfs(int now,int sumv){
int res;
if(now==n+) return res=;//已经没有剩余物品
if(sumv<v[now]) res=dfs(now+,sumv);//无法挑选第i个物品
else res=max(dfs(now+,sumv),dfs(now+,sumv-v[now])+c[now]);//比较挑和不挑的情况，选取最大的情况
return res;
}
int main(){
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++) scanf("%d%d",&v[i],&c[i]);
printf("%d",dfs(,m));
return ;
}
/*
期望得分：30分
*/
乍一看dfs好像就可以解决这个问题，那还有动态规划什么事。然而我们仔细分析一下时间复杂度，每一种状态都用选或者不选两种可能。所以我们可以得出使用dfs的时间复杂度为O(2^n)。显然这个方法不是一个很好的方法，因为这个时间复杂度太高了。我们仔细研究可以发现，造成时间复杂度这么高的原因是重复计算。既然我们找到复杂度这么高的原因，那我们就可以想办法减少它重复计算的次数。仔细分析容易想到，使用一个二维数组来记录每一次搜索的答案，这样我们就避免了重复计算。
这样的小技巧，我们称之为记忆化搜索。我们只是小小的改变就让它的时间复杂度降低至O(nW)。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e3+;
int n,m,v[N],c[N],dp[N][N*];//保存每一次搜索的答案
int dfs(int now,int sumv){
if(dp[now][sumv]!=-) return dp[now][sumv];
int res;
if(now==n+) return dp[now][sumv]=;
if(sumv<v[now]) res=dfs(now+,sumv);
else res=max(dfs(now+,sumv),dfs(now+,sumv-v[now])+c[now]);
return dp[now][sumv]=res;
}
int main(){
memset(dp,-,sizeof dp);//初始化dp数组的值，使其全为-1
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++) scanf("%d%d",&v[i],&c[i]);
printf("%d",dfs(,m));
return ;
}
/*
期望得分：60-80分
*/
仔细分析，可以发现我们还可以有更简单的写法(转成递推)：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e3+;
int n,m,v[N],c[N],dp[N][N*];
//dp[i][j] 表示取了i个物品挑选出总重量不超过j的物品时，背包中的最大价值
int main(){
memset(dp,-,sizeof dp);
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++) scanf("%d%d",&v[i],&c[i]);
for(int i=;i<=m+;i++) dp[n+][i]=;//还没开始挑选的时候，背包里的总价值为0
for(int i=n;i;i--){
for(int j=m;j>=;j--){
if(j<v[i]) dp[i][j]=dp[i+][j];
else dp[i][j]=max(dp[i+][j],dp[i+][j-v[i]]+c[i]);
}
}
printf("%d",dp[][m]);
return ;
}
/*
期望得分：60-80分
*/
然后dp[i][j]的仅由dp[i+1][j]||dp[i+1][j-v[i]]转移而来，于是我们可以滚动第一维：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e3+;
int n,m,v[N],c[N],dp[][N*];
int main(){
memset(dp,-,sizeof dp);
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++) scanf("%d%d",&v[i],&c[i]);
int now=;//开启滚动
for(int i=;i<=m;i++) dp[now][i]=;//当前状态初始化
for(int i=n;i;i--){
now^=;
for(int j=m;j>=;j--){
if(j<v[i]) dp[now][j]=dp[now^][j];
else dp[now][j]=max(dp[now^][j],dp[now^][j-v[i]]+c[i]);
}
}
printf("%d",dp[now][m]);
return ;
}
/*
期望得分：100分
*/
凡是可以滚动的，必定可以降维。——shenben
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e3+;
int n,m,v[N],c[N],dp[N*];
int main(){
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++) scanf("%d%d",&v[i],&c[i]);
dp[]=;
for(int i=;i<=n;i++){
for(int j=m;j>=v[i];j--){//v[i]以后的j对答案没有贡献
dp[j]=max(dp[j],dp[j-v[i]]+c[i]);
}
}
printf("%d",dp[m]);
return ;
}
/*
期望得分：100分
*/
使用递推方程直接求解的方法，我们称之为dp。因为他每一次的选取，都在动态的计算最优的情况。当然可能他局部不是最优，但是整体一定是最优解。这就是他和贪心算法最大的不同，贪心算法，每一次都是最优，但是整体不一定不是最优。
多重背包
问题(多重背包)：
就是一个0,,……k背包（往01背包上想就好了）
有n种重量和价值分别为vi和ci的物品，每种物品有si个。从这些物品中挑出总重量不超过m的物品，求所有挑选方案中价值总和的最大值
搜索
//期望得分：30-70分
#include<cstdio>
#include<algorithm>
#define N 10100
using namespace std;
int v[N],c[N],s[N],n,m;
int ans;
void dfs(int now,int sumv,int sumc){
if(now==n+){if(sumv<=m) ans=max(ans,sumc);return ;}
dfs(now+,sumv,sumc);
for(int i=;i<=s[now];i++) dfs(now+,sumv+i*v[now],sumc+i*c[now]);
}
int main(){
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++) scanf("%d%d%d",v+i,c+i,s+i);
dfs(,,);
printf("%d",ans);
return ;
}
记忆化搜索
//期望得分：60-100分
#include<cstdio>
#include<algorithm>
#define N 10100
using namespace std;
int v[N],c[N],s[N],n,m;
int ans;
int dp[][N];
int dfs(int now,int sumv){
if(now==n+) return ;
if(dp[now+][sumv]) dp[now][sumv]=dp[now+][sumv];
else dp[now][sumv]=dfs(now+,sumv);
for(int i=;i<=s[now];i++){
if(sumv+i*v[now]>m) break;
if(dp[now+][sumv+i*v[now]]) dp[now][sumv]=max(dp[now][sumv],dp[now+][sumv+i*v[now]]+i*c[now]);
else dp[now][sumv]=max(dp[now][sumv],dfs(now+,sumv+i*v[now])+i*c[now]);
}
return dp[now][sumv];
}
int main(){
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++) scanf("%d%d%d",v+i,c+i,s+i);
dfs(,);
printf("%d",dp[][]);
return ;
}
记忆化搜索转递推
//期望得分：60-100分
#include<cstdio>
#include<algorithm>
#define N 10100
using namespace std;
int v[N],c[N],s[N],n,m;
int ans;
int dp[][N];
int main(){
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++) scanf("%d%d%d",v+i,c+i,s+i);
for(int i=n;i;i--){
for(int j=m;j>=;j--){
for(int k=;k<=s[i];k++){
if(j-k*v[i]<) break;
dp[i][j]=max(dp[i][j],dp[i+][j-k*v[i]]+k*c[i]);
}
}
}
printf("%d",dp[][m]);
return ;
}
滚动数组（滚动第一维）
//期望得分：100分
#include<cstdio>
#include<algorithm>
#define N 10100
using namespace std;
int v[N],c[N],s[N],n,m;
int ans;
int dp[][N];
int main(){
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++) scanf("%d%d%d",v+i,c+i,s+i);
int now=;
for(int i=n;i;i--){
now^=;
for(int j=m;j>=;j--){
for(int k=;k<=s[i];k++){
if(j-k*v[i]<) break;
dp[now][j]=max(dp[now][j],dp[now^][j-k*v[i]]+k*c[i]);
}
}
}
printf("%d",dp[now][m]);
return ;
}
降维（用二进制优化）
//期望得分：100分
#include<cstdio>
#include<iostream>
using namespace std;
inline int read(){
register int x=,f=;
register char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
const int N=1e5+;
int n,m,cnt,xp[];
int f[N*],v[N],c[N];
int main(){
for(int i=;i<=;i++) xp[i]=<<i;
m=read();n=read();
for(int i=,x,y,z;i<=n;i++){
x=read();y=read();z=read();
for(int t=;z>xp[t];t++){
v[++cnt]=x*xp[t];
c[cnt]=y*xp[t];
z-=xp[t];
}
if(z>){
v[++cnt]=x*z;
c[cnt]=y*z;
}
}
for(int i=;i<=cnt;i++){
for(int j=m;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+c[i]);
}
}
printf("%d",f[m]);
return ;
}
其他背包dp自行整理