动态规划与贪婪算法

动态规划

动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

能采用动态规划求解的问题的特点：

• 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
• 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
• 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
• 从上往下分析问题，从下往上求解问题。

贪婪算法

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

解题的一般步骤是：

• 建立数学模型来描述问题；
• 把求解的问题分成若干个子问题；
• 对每一子问题求解，得到子问题的局部最优解；
• 把子问题的解局部最优解合成原来解问题的一个解。

面试题：剪绳子

题目：给你一根长度为n绳子，请把绳子剪成m段（m、n都是整数，n>1并且m≥1）。每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1]…*k[m]可能的最大乘积是多少？例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。

动态规划思路：首先定义函数f(n)把长度为n的绳子剪成若干段后各段长度乘积的最大值。在剪第一刀的时候，我们有n-1种可能的选择，也就是剪出来的第一段绳子的科能长度分别为1,2,….,n-1。因此我们可以得到f(n)=max(f(i)*f(n-i))，其中0<i<n。

这是一个从上至下的递归公式。由于递归会有很多重复的子问题，从而有大量不必要的计算。一个更好的办法是按照从下而上的顺序计算，也就是说我们先得到f(2),f(3)，再得到f(4),f(5)，直到得到f(n)。

#include <iostream>
#include <cmath>
using namespace std;
//==============动态规划============
int maxProductAfterCutting_solution1(int length)
{
    if(length < 2)
        return 0;
    if(length == 2)
        return 1;
    if(length == 3)
        return 2;

    int* products = new int[length+1];
    int Max = 0;

    products[0] = 0;
    products[1] = 1;
    products[2] = 2;
    products[3] = 3;

    for(int n=4; n<=length; ++n)
    {
        Max = 0;
        for(int i=1; i<=n/2; ++i)
        {
            int product = products[i] * products[n-i];
            if(Max<product)
                Max = product;
            products[n] = Max;
        }
    }
    Max = products[length];
    delete[] products;

    return Max;
}

贪婪算法思路：如果我们按照以下策略来剪绳子，则得到的各段长度的绳子的长度的乘积将最大：当n>=5时，我们尽量多地剪去长度为３的绳子；当剩下的绳子长度为４时，把绳子剪成两段长度为2的绳子。

//==============贪婪算法============
int maxProductAfterCutting_solution2(int length)
{
    if(length < 2)
        return 0;
    if(length == 2)
        return 1;
    if(length == 3)
        return 2;

    // 尽可能多地减去长度为3的绳子段
    int timesOf3 = length / 3;

  　 // 当绳子最后剩下的长度为4的时候，不能再剪去长度为3的绳子段。
    // 此时更好的方法是把绳子剪成长度为2的两段，因为2*2 > 3*1。
    if(length - timesOf3*3 == 1)
        timesOf3-=1;

    int timesOf2 = (length - timesOf3 * 3)/2;

    return (long int)pow(3, timesOf3) *(long int) pow(2, timesOf2);
}

int main()
{
    int length = 58;
    cout<<maxProductAfterCutting_solution1(length)<<endl;
    cout<<maxProductAfterCutting_solution2(length)<<endl;

    return 0;
}

发现一个有趣的现象，当n>58时，贪婪算法失效了，大家觉得这是什么原因呢？