JZTXT

动态规划基础

发布时间 2023-07-26 10:14:49作者: marti88414

背包问题总结

1. 01背包

求恰好装满，设为负无穷

只求最大值，设为0

for(int i=1;i<=n;i++){
    for(int j=0;j<=m;j++){
        f[i][j]=f[i-1][j];//若j<v[i]，则最大价值为在前j个物品中选总体积为j的最大价值
        if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
    }
}

一维01背包优化

for(int i=1;i<=n;i++){
    for(int j=m;j>=v[i];j--){//只枚举到v[i]可以节省时间
    	f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
}

2. 完全背包

for(int i=1;i<=n;i++) // 枚举物品
        for(int j=0;j<=v;j++) // 枚举体积
            for(int k=0;k*c[i]<=j;k++) // 三重循环 枚举每种取用件数*c[i]不大于当前总体积j
                dp[i][j]=max(dp[i][j],dp[i-1][j-c[i]*k]+w[i]*k);

完全背包一级优化

for(int i=1;i<=n;i++) // 枚举物品
        for(int j=0;j<=v;j++){//参照01背包朴素 优化为二重循环 正序枚举体积
            dp[i][j]=dp[i-1][j];
            if(j>=c[i]) dp[i][j]=max(dp[i][j],dp[i][j-c[i]]+w[i]);
        }

二级

for(int i=1;i<=n;i++) // 枚举物品
        for(int j=c[i];j<=v;j++) // 正序枚举体积
            dp[j]=max(dp[j],dp[j-c[i]]+w[i]);

3. 多重背包

for(int i=1;i<=n;i++) // 枚举物品
        for(int j=0;j<=v;j++) // 枚举体积
            for(int k=0;k<=s[i]&&k*c[i]<=j;k++) // 枚举决策
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*c[i]]+k*w[i]);

二进制优化

 int k=1; //相当于base(每组件数)：1 2 4 8 16 32 64 128 256...据此打包
        while(k<=s){
            cnt++;
            c[cnt]=k*a;
            w[cnt]=k*b;
            s-=k;
            k*=2;
        }
        if(s>0){ //若拆完之后还有零头
            cnt++; //再分一个包
            c[cnt]=a*s;
            w[cnt]=b*s;
        }
    }
    //相当于将多重背包转化为01背包
    n=cnt;//01物品总个数
    for(int i=1;i<=n;i++) 
        for(int j=v;j>=c[i];j--)//注意倒序遍历 
            dp[j]=max(dp[j],dp[j-c[i]]+w[i]);

单调队列优化

		memcpy(g, f, sizeof f);
        for (int j = 0; j < v; j ++ )
        {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v)
            {
                if (hh <= tt && q[hh] < k - s * v) hh ++ ;
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * 					w) tt -- ;
                q[ ++ tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
            }
        }

4. 分组背包

for(int i=1;i<=n;i++)
        for(int j=v;j>=0;j--) //倒序遍历
            for(int k=1;k<=s[i];k++) //每组s[i]个
                if(c[i][k]<=j) //注意判断条件！！！！！！！！！！
                    dp[j]=max(dp[j],dp[j-c[i][k]]+w[i][k]); //选或不选

5. 混合背包

if(s==0) s=v/tc; // 完全背包
        if(s==-1) s=1; // 01背包
        // 二进制优化
        int k=1;
        while(k<=s){
            cnt++;
            c[cnt]=k*tc;
            w[cnt]=k*tw;
            s-=k;
            k*=2; 
        }
        if(s>0){
            cnt++;
            c[cnt]=s*tc;
            w[cnt]=s*tw;
        }
    }
    // 将01背包 完全背包 多重背包全部打包成cnt件
    n=cnt;// 接下来就是普通的01背包啦
    for(int i=1;i<=n;i++){
        for(int j=v;j>=c[i];j--){
            dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
        }
    }

6. 二维费用的背包

for(int i=1;i<=n;i++){
        scanf("%d%d%d",&tv,&tm,&w);
        for(int j=v;j>=tv;j--){
            for(int k=m;k>=tm;k--){// 无非就是再加一维
                dp[j][k]=max(dp[j][k],dp[j-tv][k-tm]+w);
            }
        }
    }

7. 有依赖的背包问题

其实很简单 就是把线性的01背包简单变形为一棵树
链式前向星+dfs

struct node{
    int to,next;
}e[maxm];
// 链式前向星 或者叫 邻接表
//加边操作
void add(int x,int y){
    cnt++;
    e[cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt;
}

void dfs(int k){ //当前节点k
    for(int i=head[k];i;i=e[i].next){// 枚举物品
        int son=e[i].to; // 记录子节点
        dfs(son);// 向下递归到最末子树 在回溯的过程中从最末更新dp值 直到回到root
        // 由于当前节点k必选 因此体积j需要将c[k]空出来 01背包倒序枚举体积
        for(int j=v-c[k];j>=0;j--){ 
            for(int l=0;l<=j;l++){// 枚举决策
                dp[k][j]=max(dp[k][j],dp[k][j-l]+dp[son][l]);
            }//             不选son子树    选son子树
        }
    }
    for(int i=v;i>=c[k];i--) dp[k][i]=dp[k][i-c[k]]+w[k];
    for(int i=0;i<c[k];i++) dp[k][i]=0;
}

int main(){
    scanf("%d%d",&n,&v);
    for(int i=1;i<=n;i++){
        int p;
        scanf("%d%d%d",&c[i],&w[i],&p);
        if(p==-1) root=i; // 根节点
        add(p,i); // 加边加边 由父节点指向子节点
    }
    dfs(root); // 从根节点开始搜
    printf("%d",dp[root][v]);
}

8. 背包问题求方案数

求方案数类问题，我们需要调整一下dp数组的含义。以下以01背包为例：

  • dp[i][j]表示的是从前 i 个物品中选，体积不超过 j 的选法的集合。而此处为了便于方案数的计算，令dp[i][j]表示为从前 i 个物品中选，体积恰好为 j 的选法的集合。注意dp数组含义改变后需要初始化，只有当体积恰好为零时，总价值才恰好为零，即dp[0]=0，其他情况均出于未更新的状态，因此需要全部初始化为-inf。
  • dp数组的值等于此状态下的最大价值，另外我们还需要一个数组g[i][j]，表示此种状态下取最大值（即取dp[i][j]）的方案数。 最后我们只需要遍历一下dp[n][j]得到最大价值（最优方案并不一定会把背包装满 因此需要遍历），再将价值=最大价值的所有对应g[i][j]加起来，即为最优方案总数。

9. 背包问题求具体方案数

背包问题求具体方案的思路基本相同，重点在于判断每件物品到底选了还是没选，好像是废话，类似于最短路求最短路径。且由于要输出方案，所以我们不能使用空间优化后的转移方程。另外，要求输出字典序最小的方案时还须考虑选择顺序。

最长公共子序列

#include<bits/stdc++.h>
using namespace std;
int n;
int a1[100010],a2[100010];
int belong[100010];
int f[100010],b[100010],len;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a1[i]);
        belong[a1[i]]=i;
    }
    for(int i=1;i<=n;i++)
    scanf("%d",&a2[i]);
    for(int i=1;i<=n;i++)
    {
        if(belong[a2[i]]>b[len])
        {
            b[++len]=belong[a2[i]];
            f[i]=len;
            continue;
        }
        int k=lower_bound(b+1,b+len+1,belong[a2[i]])-b;
        b[k]=belong[a2[i]];
        f[i]=k;
    }
    printf("%d\n",len);
    return 0;
}

二分+子序列进阶

# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
int a[100005],t[100005],A[100005],B[100005],f[100005];
bool cmp(int a,int b)
{
    return a<b;
}
int solve(int l,int r,int x)
{
    int mid=(l+r)/2;;
    if (l==r) return l; 
    if (a[mid]>x) return solve(l,mid,x);
    if (a[mid]<=x) return solve(mid+1,r,x);
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&A[i]);
    for (int i=1;i<=n;i++) scanf("%d",&B[i]);
    for (int i=1;i<=n;i++) f[A[i]]=i;
    for (int i=1;i<=n;i++) t[i]=f[B[i]];
    memset(a,0,sizeof(a));
    for (int i=1;i<=n;i++) {
        if ((i==0)||(t[i]>a[a[0]])) a[++a[0]]=t[i];
        else if (t[i]<a[a[0]]) a[solve(1,a[0],t[i])]=t[i];
//a[lower_bound(a+1,a+a[0]+1,t[i])-a]=t[i];(替换a[solve(1,a[0],t[i])]=t[i];也行但是会稍微慢一点。。)
    }
    printf("%d\n",a[0]); 
    return 0;
}