基本动态规划
背包
完全背包
每个状态都可以从上一个阶段或者当前阶段进行转移，利用正序循环解决。
疯狂的采药
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int T,m;
int max(int &a,int &b){
return a>b?a:b;
}
int t[1000005],w[1000005],f[10000005];
signed main(){
scanf("%d%d",&T,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&t[i],&w[i]);
}
for(int i=1;i<=m;i++)
for(int j=t[i];j<=T;j++){
f[j]=max(f[j],f[j-t[i]]+w[i]);
}
cout<<f[T];
return 0;
}
多重背包
单调队列优化的多重背包
- 由于相邻的决策集合不好维护，我们按照余数来分组。
\(F[u+p*Vi]=max\{F[u+k*Vi]+(p-k)*Wi\}\)
- 按照单调队列的要求把含状态和决策的变量分开
\(F[u+p*Vi]=max\{F[u+k*Vi]-k*Wi\}+p*Wi\)
- 接下来考虑决策集合：
\(k\in[p-Ci,p-1]\)
- 因为采用了 \(0/1\) 背包的思想，对 \(p\) 倒序遍历后发现，决策集合递减。
- 需要维护一个 \(k\) 单调递减，\(F[u+k*Vi]-k*Wi\) 单调递减的单调队列
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 100,maxm = 2e4 + 100;
int V[maxn],W[maxn],C[maxn],n,m;
int f[maxm],q[maxm];
int calc(int u,int i,int k){
return f[u+k*V[i]]-k*W[i];
}
int main(){
scanf("%d%d",&n,&m);
memset(f,0xcf,sizeof f);
f[0]=0;
for(int i=1;i<=n;i++){
scanf("%d%d%d",V+i,W+i,C+i);
for(int u=0;u<V[i];u++){
int head=1,tail=0;
int maxp=(m-u)/V[i];
for(int k=maxp-1;k>=max(0,maxp-C[i]);k--){
while(head<=tail && calc(u,i,q[tail])<=calc(u,i,k))tail--;
q[++tail]=k;
}
for(int p=maxp;p>=0;p--){
while(head<=tail && q[head]>p-1)head++;
if(head<=tail)f[u+p*V[i]]=max(f[u+p*V[i]],calc(u,i,q[head])+p*W[i]);
if(p-C[i]-1>=0){
while(head<=tail && calc(u,i,q[head])<=calc(u,i,p-C[i]-1))tail--;
q[++tail]=p-C[i]-1;
}
}
}
}
int ans=-1;
for(int i=1;i<=m;i++)ans=max(ans,f[i]);
printf("%d",ans);
return 0;
}
0/1 背包
每一个状态只能从上一个状态转移过来。
采药
#include <iostream>
using namespace std;
int t[105],w[105],f[1005];
int T,M;
int max(int &a,int &b){
return a>b?a:b;
}
int main(){
cin>>T>>M;
for(int i=1;i<=M;i++)cin>>t[i]>>w[i];
for(int i=1;i<=M;i++)
for(int j=T;j>=t[i];j--){
f[j]=max(f[j],f[j-t[i]]+w[i]);
}
cout<<f[T];
return 0;
}
分组背包
对每组进行 0/1 背包的转移，每组物品要么不选要么只选一个。
- 细节
对于决策 \(k\) 循环，应该写在 \(j\) 倒序循环的内侧，才可保证状态是上一组的
P1757 通天之分组背包
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1015;
int f[maxn],a[maxn],b[maxn];
int c[1005][105],group[1005];
int n,m,cnt;
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++){
int tmp;scanf("%d%d%d",a+i,b+i,&tmp);
group[tmp]++;
cnt=max(cnt,tmp);
c[tmp][group[tmp]]=i;
}
for(int i=1;i<=cnt;i++){
for(int j=m;j>=0;j--){
for(int k=1;k<=group[i];k++){
if(j>=a[c[i][k]]){
f[j]=max(f[j-a[c[i][k]]]+b[c[i][k]],f[j]);
}
}
}
}
printf("%d\n",f[m]);
return 0;
}
树形 DP
- 一种以节点从深到浅（子树）从小到大的顺序进行的 \(DP\)
- 一般以节点编号为阶段，回溯时进行 \(DP\)
没有上司的舞会
由于需要考虑每个节点参不参加，需要增加一维 \(0/1\) 来表示状态
同上面所说进行 DP：
\(F[i,0]=\sum \ max(F[son(i),0],F[son(i),1])\)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 6e3 + 100;
struct edge{int to,nxt;}e[maxn];
int head[maxn],cnt=0;
inline void link(int u,int v){e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;}
int n,rt;
int w[maxn],f[maxn][2];
bool vis[maxn];
void dfs(int u){
f[u][0]=0;
f[u][1]=w[u];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
dfs(v);
f[u][0]+=max(f[v][0],f[v][1]);
f[u][1]+=f[v][0];
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",w+i);
for(int i=1;i<n;i++){
int k,l;
scanf("%d%d",&l,&k);
link(k,l);
vis[l]=true;
}
for(int i=1;i<=n;i++)if(!vis[i]){
rt=i;break;
}
cerr<<rt<<endl;
dfs(rt);
printf("%d\n",max(f[rt][1],f[rt][0]));
return 0;
}
选课（树形背包）
- 通常把节点作为阶段，第二维作为状态（背包容量）
- 本质是分组背包（有依赖的树形背包问题）
- 有 \(p=|son(x)|\) 组物品，每组都有 \(t-1\) 个物品，第 \(i\) 个物品的体积为 \(j\)，价值为 \(F[yi,j]\)，每棵子树都只能选择一个状态向上转移等价于每组物品选一个或者不选。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=305,maxm=305;
int head[maxn],w[maxn],f[maxn][maxn],cnt = 0,n,m;
struct Tree{
int to,nxt;
}e[maxm];
inline void link(int u,int v){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
void dp(int x){
f[x][0]=0;
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
dp(y);
for(int t=m;t>=0;t--){//倒序 (分组背包必须倒序)
for(int j=0;j<=t;j++){
if(t-j>=0){
f[x][t]=max(f[x][t],f[y][j]+f[x][t-j]);
}
}
}
}
if(x!=0){
for(int t=m;t>0;t--)f[x][t]=f[x][t-1]+w[x];//最后必须覆盖掉 ，自己占一份体积
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int pre;
scanf("%d%d",&pre,w+i);
if(pre)link(pre,i);
else link(0,i);
}
dp(0);
printf("%d",f[0][m]);
return 0;
}