• 基础算法相关笔记


    贪心

    简介

    贪心算法是从问题的初始状态出发,通过若干次的贪心选择而得到的最优值(或较优值)。

    贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,至于当前状态有关。

    适用前提是,局部最优策略能导致全局最优策略。

    常见问题

    部分背包问题

    n n n 个物体,第 i i i 个物体重量为 w i w_i wi,价值为 v i v_i vi,选择物体,每一个物体可以只取走一部分,使得总重量不超过 S S S 且总价值尽量高。

    贪心策略:先选出性价比高的。

    乘船问题

    n n n 个人,第 i i i 个人重量为 w i w_i wi,每艘船载重量为 C C C,最多可乘两人。用最少的船装载所有人。

    贪心策略:最轻的人和最重的人配对。

    区间选点问题

    Portal.

    将区间按照右端点的先后顺序排序,依次取每个区间的右端点(因为右端点可以覆盖尽量多的线段),递归操作即可。

    区间覆盖问题

    n n n 个闭区间 [ a i , b i ] [a_i,b_i] [ai,bi],选择尽量少的区间覆盖一条指定的线段区间 [ s , t ] [s,t] [s,t]

    Portal.

    将所有区间的左端点从大到小排序,每次选择覆盖点 s s s 的区间中右端点坐标最大的一个,并将 s s s 更新为该区间的右端点坐标,直到选择的区间包含 t t t 为止。

    Johnson 不等式

    一种应用于加工生产调度问题的贪心策略。

    我们先考虑两个物品 { a 1 , b 1 } , { a 2 , b 2 } \{a_1,b_1\},\{a_2,b_2\} {a1,b1},{a2,b2},先假定在 A 机器上,1 物品比 2 物品先加工,上图中的 1 和 2 分别是作业 2 在 B 机器上加工有 / 无等待的情况。

    显然有 T min ⁡ = a 1 + b 1 + a 2 + b 2 − min ⁡ ( b 1 , a 2 ) T_{\min}=a_1+b_1+a_2+b_2-\min(b_1,a_2) Tmin=a1+b1+a2+b2min(b1,a2)(相当于减掉两机器同时加工物品的情况)。对于 2 物品比 1 物品先在 A 机器加工的的情况,有 T min ⁡ = a 1 + b 1 + a 2 + b 2 − min ⁡ ( a 1 , b 2 ) T_{\min}=a_1+b_1+a_2+b_2-\min(a_1,b_2) Tmin=a1+b1+a2+b2min(a1,b2),所以按照 min ⁡ ( b 1 , a 2 ) , min ⁡ ( a 1 , b 2 ) \min(b_1,a_2),\min(a_1,b_2) min(b1,a2),min(a1,b2) 的大小降序排序即可。

    前缀和、差分

    前缀和

    一维前缀和
    二维前缀和
    • 预处理 O ( m n ) O(mn) O(mn)

      for(int i=1;i<=m;i++)
      {
          for(int j=1;j<=n;j++)
          {
              scanf("%d",&a[i][j]);
              sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
          }
      }
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
    • s[i][j]:第 i i i j j j 列格左上部分所有元素的和。
      ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 为左上角, ( x 2 , y 2 ) (x_2,y_2) (x2,y2) 为右下角的子矩阵的和为: s ( x 2 , y 2 ) − s ( x 1 − 1 , y 2 ) − s ( x 2 , y 1 − 1 ) + s ( x 1 − 1 , y 1 − 1 ) s(x_2,y_2)-s(x_1-1,y_2)-s(x_2,y_1-1)+s(x_1-1,y_1-1) s(x2,y2)s(x11,y2)s(x2,y11)+s(x11,y11)

    差分

    差分数组

    首先给定一个原数组 a a a a 1 , a 2 , a 3 , ⋯   , a n a_1,a_2,a_3,\cdots,a_n a1,a2,a3,,an,然后我们构造一个数组 b b b b 1 , b 2 , b 3 ⋯   , b i b_1,b_2,b_3\cdots,b_i b1,b2,b3,bi,使得 a i = b 1 + b 2 + b 3 + ⋯ + b i a_i=b_1+b_2+b_3+\cdots+b_i ai=b1+b2+b3++bi
    也就是说, a a a 数组是 b b b 数组的前缀和数组,反过来我们把 b b b 数组叫做 a a a 数组的差分数组。换句话说,每一个 a i a_i ai 都是 b b b 数组中从头开始的一段区间和。

    差分
    1. 一维差分

      a a a 数组中的 [ l , r ] [l,r] [l,r] 区间中的每一个数都加上 c c c,只需对差分数组 b b bb[l]+=c,b[r+1]-=c 。时间复杂度为 O ( 1 ) O(1) O(1)

    2. 二维差分

      s[x1][y1]+=c,s[x2+1][y1]-=c,s[x1][y2+1]-=c,s[x2+1][y2+1]+=c;
      
      • 1

    递归

    卡特兰数

    卡特兰数,又称卡塔兰数(Catalan Number),是组合数学中一个常用的数列。其前几项为: 1 , 2 , 5 , 14 , 42 , 132 , 429 , 1430 , 4862 , ⋯ \boxed{1,2,5,14,42,132,429,1430,4862,\cdots} 1,2,5,14,42,132,429,1430,4862,

    1. f ( n ) = ∑ i = 0 n − 1 f ( i ) × f ( n − i − 1 ) f(n)=\sum_{i=0}^{n-1}f(i)\times f(n-i-1) f(n)=i=0n1f(i)×f(ni1)

    2. f ( n ) = f ( n − 1 ) × ( 4 × n − 2 ) n + 1 f(n)=\dfrac{f(n-1)\times(4\times n-2)}{n+1} f(n)=n+1f(n1)×(4×n2)

    卡特兰数的组合数学公式,详见组合数学

    汉诺塔问题

    1. 移动 n n n 个盘子需要 2 n − 1 2^{n-1} 2n1 步。
    2. f i f_i fi 为移动 i i i 个盘子的最少步数,有 f i = 2 × f i − 1 + 1 f_i=2\times f_{i-1}+1 fi=2×fi1+1

    排序

    基数排序

    基数排序,是桶排序的扩展。它的基本思想是,把整数按位切割,从低位到高位排序。

    具体实现就是将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后从最低位开始,依次进行一次排序。从最低位排序到最高位排序完成以后,数列就变成一个有序序列。

    总结

  • 相关阅读:
    C#【高级篇】 C# 多线程
    Qt+ECharts开发笔记(一):ECharts介绍、下载和Qt调用ECharts基础柱状图Demo
    bean的生命周期(最全最细讲解)
    Springboot项目 导出生成jar包
    如何杀死服务器出现的僵尸进程
    新书速览|机器学习实战:视频教学版
    asp.net+sqlserver汽车4s店销售网站系统c#项目
    基于燃压缩空气储能系统的零碳微能源互联网优化调度(Matlab代码实现)
    ESP32控制器使用SX1278 LoRa模块的方法
    美团面试,被拷打了一小时....
  • 原文地址:https://blog.csdn.net/ncwzdlsd/article/details/133971861