首页 > 其他分享 >动态规划基础

动态规划基础

时间：2023-07-26 10:26:30浏览次数：40  
标签：cnt 背包 int 基础 len -- 动态 规划 dp

背包问题

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;
}

最长公共子序列(LCS)

#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;
}

状压dp

状态压缩动态规划，就是我们俗称的状压DP，是利用计算机二进制的性质来描述状态的一种DP方式。

例题：luogu P1896 [SCOI2005] 互不侵犯
简述：给一个 \(n \times n\) 的矩阵放置棋子，每个棋子周围的八个空间不能有棋子，询问有多少种放置方法
状态定义：\(dp_{i,j,k}\) 表示在第 \(i\) 行，棋子状态是 \(j\) 时，放置了 \(k\) 个棋子的最多情况
状态转移：\(dp[i][sit][j] += dp[i - 1][sit2][j - c(sit)];\)
时间复杂度：\(O(n^4)\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 15;
int n, k;
int dp[N][1 << 9][N * N];

inline int c(int sit) {
    return __builtin_popcount(sit);
}

//  检查是否符合放置要求
bool check(int sit, int sit2) {
    for(int i = 0; i < n - 1; ++i) {
        if((sit & (1 << i)) && (sit & (1 << (i + 1)))) return false;
    }
    if((sit & (sit2 << 1)) || (sit & (sit2 >> 1)) || (sit & sit2)) return false;
    return true;
}



inline void solve() {
    std::cin >> n >> k;
    for(int i = 0; i < n; ++i) {
        for(int sit = 0; sit < (1 << n); ++sit) {
		// sit表示每一行的状态，状压dp核心
            if(!check(sit, 0)) continue;
            if(i == 0) dp[i][sit][c(sit)] = 1;
            else {
                for(int j = c(sit); j <= k; ++j) {
                    for(int sit2 = 0; sit2 < (1 << n); ++sit2) {
                        if(!check(sit2, 0) || !check(sit, sit2)) continue;
                        dp[i][sit][j] += dp[i - 1][sit2][j - c(sit)];
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int sit = 0; sit < (1 << n); ++sit) {
        ans += dp[n - 1][sit][k];
    }
    std::cout << ans << endl;
    return;
}


signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T;
    T = 1;
    while(T --) {
        solve();
    }
}

区间DP

例题：luogu P1880 [NOI1995] 石子合并
简述：N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最大/小代价。
状态定义：\(dp_{i,j}\) 表示区间 \([i, j]\) 合并所能得到的最大/小代价
状态转移：\(dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+weigth[i][ends]);\)

dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+weigth[i][ends]);

时间复杂度：\(O(n^3)\)

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;

const int N = 3e2 + 10;
const int M = 1e6 + 10;

int n, m;
int a[N];
int dpmax[N][N], dpmin[N][N];
int sum[N];

inline void solve() {
    scanf("%lld", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        a[i + n] = a[i];

    }
    for(int i = 1; i <= 2 * n; ++i) {
        sum[i] = sum[i - 1] + a[i];
    }

    for(int len = 2; len <= n; ++len) {
        for(int i = 1; i <= 2 * n - len + 1; ++i) {
            int j = len + i - 1;
            dpmax[i][j] = -1, dpmin[i][j] = inf;
            for(int k = i; k < j; ++k) {
                dpmax[i][j] = max(dpmax[i][j], dpmax[i][k] + dpmax[k + 1][j] + sum[j] - sum[i - 1]);
                dpmin[i][j] = min(dpmin[i][j], dpmin[i][k] + dpmin[k + 1][j] + sum[j] - sum[i - 1]);
            }
        }
    }
    int maxx = -1;
    int minn = inf;
    for(int i = 1; i < n; ++i) {
        maxx = max(maxx, dpmax[i][i + n - 1]);
        minn = min(minn, dpmin[i][i + n - 1]);
    }
    printf("%lld\n%lld\n", minn, maxx);
}

signed main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0), cout.tie(0);

    int T;
    T = 1;
    while(T--) {
        solve();
    }
    return 0;
}

数位DP

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 15
int num;
int* a = new int[maxn];
int f[15];
//int a[maxn];
int b[maxn];//b保存第p为存的是那个数
int ten[maxn];
int L, R;
int t;
int dfs(int p, bool limit) {//p表示在第p位，limite表示此时是否处于限制位
	if (p < 0) {
		//for (int i = 2; i >= 0; i--)cout << b[i];//无限递归,记得加结束return
		//cout << endl;
		return 0;//搜索结束，返回
	}
	if (!limit && f[p] != -1) {//记忆化搜索，不处于限制位，并且f[p]被算过了
		return f[p];
	}
	int up = limit ? a[p] : 9;//判断是否处于限制位，如果是就只能取到a[p]为，否则最高位能取到9
 
	int ans = 0;
 
	for (int i = 0; i <= up; i++) {
		//b[p] = i;
		if (i == 3) {
			if (limit && i == up) {
				ans += 1;
				for (int j = p - 1; j >= 0; j--)//处于限制条件就把限制数下面全算上
					ans += a[j] * ten[j];
			}
			else//如果不处于限制条件直接加上10的p次方
				ans += ten[p];
		}
		else ans += dfs(p - 1, limit && i == up);//这里填a[p]可以填up也行，在处于限制的时候up等于a[p]
 
	}
	if (!limit)//记忆化搜索，如果没有处于限制条件就可以直接那算过一次的数直接用，能节省很多时间
		f[p] = ans;
	return ans;
}
 
int handle(int num) {
	int p = 0;
	while (num) {//把num中的每一位放入数组
		a[p++] = num % 10;
		num /= 10;
	}
	//说明a数组写进去了，但是读取无效数据是什么意思勒，之前好像不是这样的，解决办法，动态创建数组
	/*for (int i = 0; i < p; i++) {
		cout << a[i];
	}*/
	return dfs(p - 1, true);//对应的最高位为p-1位，为True表示没有处于限制位
}
 
void init() {
	ten[0] = 1;
	for (int i = 1; i < 15; i++) {
		ten[i] = ten[i - 1] * 10;
	}
	memset(f, -1, sizeof(f));
}
int32_t  main() {
	cin>>t;
    while(t--){
        cin>>L>>R;
        //handle(23);
	    init();//一定要记得初始化，TM的我在这卡了半个月
	    cout << handle(R)-handle(L) << endl;
	    delete[]a;
    }
    return 0;
}

概率DP

顾名思义，概率DP就是动态规划求概率的问题。一般来说，我们将dp数组存放的数据定义为到达此状态的概率，那么我们初值设置就是所有初始状态概率为1，最终答案就是终末状态dp值了。

我们在进行状态转移时，是从初始状态向终末状态顺推，转移方程中大致思路是按照当前状态去往不同状态的位置概率转移更新DP，且大部分是加法。

标签：cnt,背包,int,基础,len,--,动态,规划,dp
From： https://www.cnblogs.com/marti88414/p/17581724.html

相关文章

  • Qt+GDAL开发笔记（一）：在windows系统mingw32编译GDAL库、搭建开发环境和基础Demo
    前言  麒麟系统上做全球北斗定位终端开发，调试工具要做一个windows版本方便校对，北斗GPS发过来的是大地坐标，应用需要的是经纬度坐标，所以需要转换，可以使用公式转换，但是之前涉及到了另一个shang市公司项目使用WG，最终选择了GDAL库进行转换。注意  如果读者不强制要求ming......
  • MyBatis-Plus这样实现动态SQL
    拦截器介绍拦截器是一种基于AOP（面向切面编程）的技术，它可以在目标对象的方法执行前后插入自定义的逻辑。MyBatis定义了四种类型的拦截器，分别是：Executor：拦截执行器的方法，例如update、query、commit、rollback等。可以用来实现缓存、事务、分页等功能。ParameterHandler：拦截参......
  • python学习01：Python基础语法与数据类型
    一、Python注释通常用于解释代码，这段打开主要是想表达什么意思，注释后的代码不会再代码中运行，例如：#打印HelloWorldprint("HelloWorld")注释的方式：#python注释（快捷键：Ctrl+/（选中你想注释的代码就可全部注释掉））=========>单行注释''''print('hello') ''''''�......
  • day10 10.1 C语言基础之编译器安装
    【一】学习C语言的原因一般公司的apk基于Java实现的加密jadx反编译java，分析代码NB公司的的apk，基于Java+C语言实现加密（JNI开发）加密一般使用C语言开发，在安卓项目中使用Java调用C语言开发的动态链接库文件jadx反编译java，分析代码看不到加密ida反编译c语言，分析代码......
  • 01 linux基础（1）
    环境安装解压，从vmware打开虚拟机。设置密码：1打开终端：ctrl+alt+tlinux介绍Linux的发展1）1969年，由kenthompson在AT&T贝尔实验室实现的。使用的是汇编语言。2）1970年，KenThompson和DennisRitchie是使用C语言对整个系统进行了再加工和编写，是的Unix能够很容易的移植到其他硬件的......
  • 02 linux 基础（2）
    shell基本维护命令获取联机帮助使用man命令可以找到特定的联机帮助页，并提供简短的命令说明。一般语法格式为：联机帮助页提供了指定命令commandname的相关信息，包括：名称、函数、语法以及可选参数描述等。无论帮助有多长，都遵循这个格式显示。在页面很多的情况下使用PageUp......
  • 动态导入模块
    1.创建一个简单的hello文件，里面只有一个类A，A属性为name 2.获取文件下面的未知类有哪些？当只知道需要导入的类名称，但是不知道具体位置，如何动态导入？importimportlib.utilimportinspect#文件夹下面有个脚本，下面只有一个类:fromtest_importimporthello#给定文件，获取......
  • AI训练营—Python的一些基础知识
    目录列表字典复制对象列表切片：左开右闭倒取值字典集合：无序的，元素是唯一的dk_set=set()#也可以是dk_set={},创建一个空的集合#集合的并union()，交intersection()，差difference()#集合不会出现重复元素foriin"Dkfor3,Dkfor3":dk_set.add(i)#添加元素i的值进集合......
  • Asp.Net 使用Log4Net (基础版)
    Asp.Net使用Log4Net(基础版)1.创建项目创建ASP.NETWebForms项目在VisualStudio中创建一个新的ASP.NETWebForms项目。命名为"Log4NetDemo"。2.安装Log4Net包打开NuGet包管理器控制台，并运行以下命令来安装Log4Net：mathematicaCopycodeInstall-Packagelog4net3.添......
  • python动态加载py文件
    动态加载py文件的实现对于刚入行的小白来说，实现动态加载py文件可能是一个比较陌生的概念。不过不用担心，我会帮助你逐步了解和掌握这个过程。流程概述动态加载py文件的实现可以分为以下几个步骤：找到要加载的py文件的路径。动态加载py文件。调用加载的py文件中的函数或类。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99