动态规划
##一、定义
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
与贪心的区别：我们在得到当前最优解的时候，需不需要使用前面的阶段中的得到的值，如果不需要，那就是贪心；如果需要，就是动归。
例1：Luogu P1216
#include <iostream>
#define MAX 1005
using namespace std;
int tower[MAX][MAX],n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin>>tower[i][j];
for(int i=n-1;i>=1;i--)
for(int j=1;j<=i;j++)
tower[i][j]+=max(tower[i+1][j],tower[i+1][j+1]);
cout<<tower[1][1]<<endl;
}
例2：HDU P1176
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 100005
using namespace std;
int n,x,T,dp[MAX][15],maxt;
inline int max3(int a,int b,int c)
{
return max(max(a,b),c);
}
int main()
{
while(~scanf("%d",&n))
{
memset(dp,0,sizeof(dp));
maxt=-1;
if(n==0)
break;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x,&T);
if(maxt<T)
maxt=T;
dp[T][x]++;
}
for(int i=maxt-1;i>=1;i--)
{
dp[i][0]+=max(dp[i+1][0],dp[i+1][1]);
dp[i][10]+=max(dp[i+1][10],dp[i+1][9]);
for(int j=1;j<=9;j++)
dp[i][j]+=max3(dp[i+1][j+1],dp[i+1][j],dp[i+1][j-1]);
}
printf("%d\n",max3(dp[1][4],dp[1][5],dp[1][6]));
}
return 0;
}
二、背包问题
1.01背包
定义
01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2至Wn，与之相对应的价值为P1,P2至Pn。
01背包是背包问题中最简单的问题。
01背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。
在01背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。
如果不选择将其放入背包中，则不需要处理。如果选择将其放入背包中，由于不清楚之前放入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。
做法
用子问题定义状态：f[i][v]表示在前 i 件物品中选择若干件放在已用空间为 v 的背包里所能获得的最大价值
状态转移方程：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}（c[i]表示第i件商品的体积，w[i]表示第i件商品的价值）
例1：Luogu P2871（代码与题目略有不同）
#include <iostream>
#define MAX 12885
int tot_v,n,v[MAX],c[MAX],dp[MAX][MAX];
using namespace std;
int main()
{
cin>>tot_v>>n;
for(int i=1;i<=n;i++)
cin>>v[i];
for(int i=1;i<=n;i++)
cin>>c[i];
for(int i=1;i<=n;i++)
for(int j=v[i];j<=tot_v;j++)
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+c[i]);
cout<<dp[n][tot_v];
}
空间优化：
#include <iostream>
#define MAX 12885
using namespace std;
int dp[MAX],v[MAX],c[MAX],tot_v,n;
int main()
{
cin>>tot_v>>n;
for(int i=1;i<=n;i++)
cin>>v[i];
for(int i=1;i<=n;i++)
cin>>c[i];
for(int i=1;i<=n;i++)
for(int j=tot_v;j>=v[i];j--)//每个物品只能拿一次，如果从前往后就会买多次
dp[j]=max(dp[j],dp[j-v[i]]+c[i]);
cout<<dp[tot_v];
}
例2：HDU P1248
#include <iostream>
using namespace std;
int n,dp[100005],t,res[105];
int main()
{
const int price[4]={0,150,200,350};
cin>>t;
for(int k=1;k<=t;k++)
{
cin>>n;
for(int i=1;i<=3;i++)
for(int j=price[i];j<=n;j++)
dp[j]=max(dp[j],price[i]+dp[j-price[i]]);
cout<<n-dp[n]<<endl;
}
return 0;
}
例3：HDU P1203
法一：
#include <iostream>
#include <cstdio>
#define MAX 10005
using namespace std;
int n,m,a[MAX];
double b[MAX],dp[MAX],res;
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n==0&&m==0)
break;
for(int i=1;i<=m;i++)
cin>>a[i]>>b[i];
for(int i=0;i<=n;i++)//注意从零开始赋初始值！！！
dp[i]=1;//或用memset(dp,1,sizeof(dp));
for(int i=1;i<=m;i++)
for(int j=n;j>=a[i];j--)
dp[j]=min(dp[j],dp[j-a[i]]*(1-b[i]));
printf("%.1lf%%\n",(1-dp[n])*100);
}
}
法二：
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 10005
using namespace std;
int n,m,a[MAX];
double b[MAX],dp[MAX],res;
inline double work(double a,double b)
{
return 1-(1-a)*(1-b);
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n==0&&m==0)
break;
for(int i=1;i<=m;i++)
cin>>a[i]>>b[i];
memset(dp,0,sizeof(dp));//注意归零！！！
for(int i=1;i<=m;i++)
for(int j=n;j>=a[i];j--)
dp[j]=max(dp[j],work(dp[j-a[i]],b[i]));
printf("%.1lf%%\n",dp[n]*100);
}
}
2.完全背包
定义
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
做法
思路： 1.将完全背包转换成01背包（空间复杂度大，不推荐）
用总容积除以每种物品的体积，为n，将每种物品拆分成有相同价值的n件物品
2.直接用完全背包做
状态转移方程：
f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}（c[i]表示第i件商品的体积，w[i]表示第i件商品的价值）
注意：max函数内第二个参数是f[i][v-c[i]]+w[i]，因为可以重复拿同一件物品。
例1：Luogu P2722
未经优化（会超内存）
#include <iostream>
#define MAX 10005
using namespace std;
int m,n,score[MAX],time[MAX],dp[MAX][MAX];
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>score[i]>>time[i];
for(int i=1;i<=n;i++)
for(int j=time[i];j<=m;j++)
dp[i][j]=max(dp[i-1][j],dp[i][j-time[i]]+score[i]);
cout<<dp[n][m]<<endl;
}
#include <iostream>
#define MAX 10005
using namespace std;
int m,n,time[MAX],score[MAX],dp[MAX];
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>score[i]>>time[i];
for(int i=1;i<=n;i++)
for(int j=time[i];j<=m;j++)
dp[j]=max(dp[j],dp[j-time[i]]+score[i]);
cout<<dp[m]<<endl;
}
延伸阅读：崔添翼-背包问题九讲
