MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » 算法-枚举谋略

算法-枚举谋略

www.MyException.Cn  网友分享于:2015-02-03  浏览:0次
算法--枚举策略

本文地址:http://www.cnblogs.com/archimedes/p/algorithm-enumeration.html,转载请注明源地址。

枚举法的基本思想

枚举法的基本思想是根据提出的问题枚举所有可能状态,并用问题给定的条件检验哪些是需要的,哪些是不需要的。能使命题成立,即为其解。

枚举结构:循环+判断语句。 

枚举法的条件

虽然枚举法本质上属于搜索策略,但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件:

⑴可预先确定每个状态的元素个数n;

⑵状态元素a1,a2,…,an的可能值为一个连续的值域。

枚举法的框架结构

设ai1—状态元素ai的最小值;aik—状态元素ai的最大值(1≤i≤n),即a11≤a1≤a1k,a21≤a2≤a2k, ai1≤ai≤aik,……,an1≤an≤ank

for a1←a11 to a1k do
     for a2←a21 to a2k do  
         ……………………
              for ai←ai1 to aik do
                   ……………………
                       for an←an1 to ank do
                             if 状态(a1,…,ai,…,an)满足检验条件
                                                   then 输出问题的解;

枚举法的优缺点

枚举法的优点:

⑴由于枚举算法一般是现实生活中问题的“直译”,因此比较直观,易于理解

⑵由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上,所以算法的正确性比较容易证明

枚举法的缺点:

枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价,因此效率比较低

直译”枚举:直接根据题意设定枚举对象、范围和约束条件。

注意认真审题,不要疏漏任何条件

举例

例题1:砝码称重

【问题描述】设有1g、2g、3g、5g、10g、20g的砝码各若干枚(其总重<=1000),求用这些砝码能称出不同的重量个数。

【文件输入】输入1g、2g、3g、5g、10g、20g的砝码个数。

【文件输出】输出能称出不同重量的个数。

【样例输入】1 1 0 0 0 0

【样例输出】3

【分析】根据输入的砝码信息,每种砝码可用的最大个数是确定的,而且每种砝码的个数是连续的,能取0到最大个数,所以符合枚举法的两个条件,可以使用枚举法。枚举时,重量可以由1g,2g,……,20g砝码中的任何一个或者多个构成,枚举对象可以确定为6种重量的砝码,范围为每种砝码的个数。判定时,只需判断这次得到的重量是新得到的,还是前一次已经得到的,即判重。由于重量<=1000g,所以,可以开一个a[1001]的数组来判重。

C++代码如下:

#include <iostream>
using namespace std;
int A[1001]={0};
int main( )
{
    int a,b,c,d,e,f,i,sum,num;
    int arr[7];
    int w[7]={0,1,2,3,5,10,20};
    cin>>a>>b>>c>>d>>e>>f;
    for(arr[1]=0; arr[1]<=a; arr[1]++)
        for(arr[2]=0; arr[2]<=b; arr[2]++)
            for(arr[3]=0; arr[3]<=c; arr[3]++)
                for(arr[4]=0; arr[4]<=d; arr[4]++)
                    for(arr[5]=0; arr[5]<=e; arr[5]++)
                        for(arr[6]=0; arr[6]<=f; arr[6]++) {
                            sum=0;
                            for(i=1; i<=6; i++) {
                                sum+=arr[i]*w[i];
                                A[sum]=1;
                            }
                        }
    num=0;
    for(i=1; i<=1000; i++) {
        if(A[i]==1)
            num++;
    }
    cout<<num<<endl;return 0;
}

例题2:火柴棒等式

【问题描述】给你n根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示:

注意:

     1. 加号与等号各自需要两根火柴棍

     2. 如果A≠B,则A+B=C与B+A=C视为不同的等式(A、B、C≥0)

     3. n根火柴棍必须全部用上

【输入】输入一个整数n(n≤24)。

【输出】输出能拼成的不同等式的数目。 

问题简述:给你n(n<=24)根火柴棒,叫你拼出 “A + B = C”这样的等式,求方案数。

思路:本题最多24根火柴,等号和加号共用4根火柴,所以A,B,C这3个数字需用20根火柴。我们考查A和B的最大的取值可能:0~9这10个数字所用的火柴数为6,2,5,5,4,5,6,3,7,6,很明显数字1用的火柴棒最少只要2根,不妨让B为1,那么A和C最多可以使用18根火柴,而C>=A,满足条件的A的最大取值为1111。所以枚举A和B的范围是从0~1111。

为了加快速度,可以将0到2222的所有整数需要的火柴棒数目提前算好保存在数组中。

代码如下:

#include <iostream>
using namespace std;
int a[2223]={6,2,5,5,4,5,6,3,7,6};
const int b[10]={6,2,5,5,4,5,6,3,7,6};
//计算自然数n所需要的火柴数
int need(int n)
{
    int tmp, num;
    num=0;
    if(n==0) return 6;
    while(n>0) {
        tmp=n%10;
        num+=b[tmp];
        n/=10;
    }
    return num;
}

int main( )
{
    int n,A,B,C,D,sum;
    cin>>n;
    sum=0;
    for(int i=10; i<2223; i++) //预处理
        a[i]=need(i);
    for(int i=0; i<=1000; i++) {
        for(int j=0; j<=1000; j++) {
            A=a[i];   B=a[j];  C=n-4-A-B;
            D=a[i+j];
            if(D==C) sum++;
        }
    }
    cout<<sum<<endl;
    system("PAUSE");
    return 0;
}

枚举算法的优化

枚举算法的时间复杂度:状态总数*单个状态的耗时。

⑴提取有效信息;

⑵减少重复计算;

⑶将原问题化为更小的问题;

⑷根据问题的性质进行截枝;

⑸引进其他算法

举例

【例题3】给你n(n<=105)个整数,然后要有m (m<=105)个询问。每个询问两个整数i和j,问第i个数字到第j个数字所有数字之和。

朴素算法:

#include <iostream>
using namespace std;
int main( )
{
    int sum,n,m,x,y,i,j,a[106];
    cin>>n>>m;
    for(i=1; i<=n; i++)  cin>>a[i];
    for(i=1; i<=m; i++) {
        cin>>x>>y;
        sum=0;
        for(j=x; j<=y; j++)  sum+=a[j];
        cout<<sum<<endl;
    }
    return 0;
}

优化算法:

 先计算s[i]=s[i-1]+a[i]

 cin>>n;
 for(i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];}
 for(i=1;i<=m;i++)
 {  cin>>x>>y;
    cout<<s[y]-s[x-1]<<endl;
 }

【例题4】最大子矩阵问题

【问题描述】给定一个二维的数组(含正数或负数),请从中找出和最大的子矩阵。例如:

方法1:“直译”枚举过程

for(x1=1;x1<=n;x1++)//枚举矩形左上角(x1,y1)
    for(y1=1;y1<=n;y1++)
          for(x2=1;X2<=n;X2++)//枚举矩形右下角(x2,y2)
                for(y2=1;y2<=n;y2++)
                  考察状态左上角为(x1,y1)右下角为(x2,y2)内矩形的元素之和;

设map为数字矩阵;sum为当前矩形内元素的和;best为最优解。考察过程如下:

sum=0for(x=x1;x<=x2;x++)//计算当前矩形内元素的和
      for(y=y1;y<=y2;y++)sum=sum+map[x][y];
              if(sum>best)best=sum;//调整最优解

这个算法相当粗糙,枚举状态的费用为O(n6)

方法2:从减少重复计算入手

有刚才一维情况可以推广到二维,在统计左上角为(x1,y1)右下角为(x2,y2)内矩形的元素之和时,我们同样可以先初始化,计算出左上角为(1,1)右下角为(x,y)内矩形的元素之和s[x][y]。

for(x1=1;x1<=n;x1++)//枚举矩形左上角(x1,y1)
{    
    for(y1=1;y1<=n;y1++) {    
        cin>>map[i][j];
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+map[i][j];
    }
}

对于状态左上角为(x1,y1)右下角为(x2,y2)内矩形的元素之和,可以改为:

sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
if(sum>best)best=sum;//调整最优解

由于利用了计算出的结果,整个算法的时间复杂度降为O(n4)

方法3:提取恰当的信息

容易观察到,最大子矩阵问题是最大连续子序列和问题的提升,即将一条线换成一个面,将一维问题提升到二维问题。所以我们计算最大子矩阵的方法就是将一行行的数进行累加以求得最大值。

但是还有一个问题,那就是应该如何高效地存储矩阵?

我们可以想到:在一个一维的数列中,设数组b[i]表示从第1个元素到第i个元素的和,则如果想要求第i个元素到第j个元素的和,只需要计算b[j]-b[i-1]的值就行了。由此推广到二维矩阵,设b[i][j]表示矩阵第j列前i个元素的和,a[i][j]表示元素数据,则压缩存储:

for(i=1;i<=n;i++)
   for(j=1;j<=n;j++){cin>>a[i][j];b[i][j]=b[i-1][j]+a[i][j];}

因此,我们可以使用三重循环求出所有的矩形值,即枚举起始行i和终止行j,压缩子矩形成为一行,变成一维求最大字段和问题。

即t[k]=max(t[k-1],0)+b[j][k]-b[i-1][k];

时间复杂度为O(n3)

核心代码:

sum=-0x7fffffff;
for(i=1;i<=n;i++)  //阶段:起始行
{    
    for(j=i;j<=n;j++)  //状态:结束行
     {    
         t[1]=b[j][1]-b[i-1][1];  //初始化第1列的值
         for(k=2;k<=n;k++)  //决策:第几列
         {     
             t[k]=max(t[k-1],0)+b[j][k]-b[i-1][k];
             if(t[k]>sum)sum=t[k];
         }
      }
}
cout<<sum<<endl;

 

文章评论

 程序员的样子
程序员的样子
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
为什么程序员都是夜猫子
为什么程序员都是夜猫子
总结2014中国互联网十大段子
总结2014中国互联网十大段子
我的丈夫是个程序员
我的丈夫是个程序员
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
10个调试和排错的小建议
10个调试和排错的小建议
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
老程序员的下场
老程序员的下场
程序员必看的十大电影
程序员必看的十大电影
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
旅行,写作,编程
旅行,写作,编程
编程语言是女人
编程语言是女人
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
程序员应该关注的一些事儿
程序员应该关注的一些事儿
我是如何打败拖延症的
我是如何打败拖延症的
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
Java程序员必看电影
Java程序员必看电影
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
那些争议最大的编程观点
那些争议最大的编程观点
程序员的鄙视链
程序员的鄙视链
程序员都该阅读的书
程序员都该阅读的书
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
一个程序员的时间管理
一个程序员的时间管理
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
如何成为一名黑客
如何成为一名黑客
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
代码女神横空出世
代码女神横空出世
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
程序员和编码员之间的区别
程序员和编码员之间的区别
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有