三分法

三分法

在之前的几周中我们了解到二分法作为分治中最常见的方法,适用于单调函数,逼近求解某点的值。
但当函数是凸形函数时,二分法就无法适用,这时就需要用到三分法。
从三分法的名字中我们可以猜到,三分法是对于需要逼近的区间做三等分:
三分法
我们发现lm这个点比rm要低,那么我们要找的最小点一定在[left,rm]之间。如果最低点在[rm,right]之间,就会出现在rm左右都有比他低的点,这显然是不可能的。 同理,当rm比lm低时,最低点一定在[lm,right]的区间内。
利用这个性质,我们就可以在缩小区间的同时向目标点逼近,从而得到极值。

最大子段和(不同解法)

问题描述

最大子段和:给定n个整数(可以有负数),求出其最大连续的子段的和,如果全部都为负数,那么结果为0。

穷举法

思想

将所有子段可能的情况穷举出来,分别求出子段和,得到最大值,如果最大值为负数,取最大值为0.

代码实现

时间复杂度

O(n^2 )

分治算法

思想

将a[0,n]分为a[0,n/2]和a[n/2+1,n],a[0,n]有三种情况:

  1. 第一种情况与a[0,n/2]相同;
  2. 第二种情况与a[n/2+1,n]相同;
  3. 第三种情况是a[0,n/2]情况与a[n/2+1,n]情况的和。
    所以实现代码时,只要通过计算第三种情况与第一、二种情况的大小,就可以得到最大子段和。

    代码实现

    用C++实现,如下所示:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    #include<iostream>
    using namespace std;
    int MaxSub(int v[], int l, int r);

    int main()
    {

    int v[10] = {1, 2, -4, 4, 5, -6, 7, 8, -9, 0};
    int l = 0, r = 9;
    cout << MaxSub(v, l, r) <<endl;
    return 0;
    }

    int MaxSub(int v[], int l, int r)
    {

    if(l == r)
    {
    return v[l] > 0 ? v[l] : 0;
    }
    int m = (l + r) / 2;
    int lsum = MaxSub(v, l, m);
    int rsum = MaxSub(v, m + 1, r);

    int maxl = 0;
    int sum = 0;
    for(int i = m; i >= l; i--)
    {
    sum += v[i];
    if(sum > maxl)
    {
    maxl = sum;
    }
    }

    int maxr = 0;
    sum = 0;
    for(int j = m+1; j <= r; j++)
    {
    sum += v[j];
    if(sum > maxr)
    {
    maxr = sum;
    }
    }
    sum = maxl + maxr;
    if(lsum > sum)
    {
    sum = lsum;
    }
    if(rsum > sum)
    {
    sum = rsum;
    }
    return sum;
    }

时间复杂度

O(nlog(n))

动态规划实现

思想

数组从头开始遍历,逐个累加,如果累加的和小于0,则和置为0,继续累加,记录最大sum,返回最大的sum。

代码实现

用C++实现,如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;

int main()
{

int a[10] = {1, 2, -4, 4, 5, -6, -7, 8, -9, 0};
int i, max = 0, sum = 0;
int len = sizeof(a) / sizeof(a[0]);
for(i = 0; i < len; i++)
{
if(sum < 0)
{
sum = 0;
}
sum += a[i];
max = sum > max ? sum : max;
}
cout << max << endl;
return 0;
}

复杂度

O(n)

算法分析(动态规划)

基本概念

动态规划的过程:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生的。所以,这种多阶段最优化决策解决问题的过程就称为动态规划。

使用动态规划技术的必要条件

一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列。

经典例子分析

最长公共子序列

题目:设X和Y是两个序列,其中
X=
Z=
如果Z中元素所有元素都在X中存在,且先后顺序不变,那么Z是X的子序列。Z含有的元素个数,称为子序列长度。
那么给定序列
X=
Y=
求X和Y的最长公共子序列。
下面是用C++实现的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<vector>
using namespace std;

int main()
{

vector<char> vec1;
vector<char> vec2;
char ch1, ch2;
int c[100][100], b[100][100], i, j;
while(1)
{
cin >> ch1;
if(ch1 == '0') break;
vec1.push_back(ch1);
}
while(1)
{
cin >> ch2;
if(ch2 == '0') break;
vec2.push_back(ch2);
}

vector<char>::iterator it1 = vec1.begin();
vector<char>::iterator it2 = vec2.begin();

for(i = 0; i <= vec1.size(); i++)
{
c[i][0] = 0;
}
for(i = 0; i <= vec2.size(); i++)
{
c[0][i] = 0;
}
for(i = 1, it1 = vec1.begin(); it1 != vec1.end(); it1++, i++)
{
for(j = 1, it2 = vec2.begin(); it2 != vec2.end(); it2++, j++)
{
if(*it1 == *it2)
{
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
}
else if(c[i-1][j] >= c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
cout << c[vec1.size()][vec2.size()] << endl;
return 0;
}

背包问题

背包问题(Knapsack Problem)是一个著名的NP难问题。
题目:一个旅行者准备随身携带一个背包。可以放入背包的物品有n种,物品j的重量和价值分别为wj,vj,j=1,2,…,n。如果背包的最大重量限制为b,怎样选择放入背包的物品以使得背包的价值最大?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<vector>
using namespace std;

int main()
{

vector<float> weight;
vector<float> value;
float w, v;
while(1)
{
cin >> w >> v;
if(w == 0 && v == 0)
{
break;
}
weight.push_back(w);
value.push_back(v);
}