动态规划1_蛮力解sas代码_Andy的原创帖4

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

参考:
摘自July《编程之法：面试和算法心得》第5.1节http://mp.weixin.qq.com/s?_biz=MzA4MTczMDA4OA==&mid=402193562&idx=1&sn=4de8c4533bc4f5d897579be0ead106f0#rd

************************************************************************************************
看到上面的帖子，打算研究一下动态规划的实现。似乎百度上仍然找不到关于SAS实现的代码，自己研究了一下，供有兴趣的Sasor参考。

最大连续乘积子数组:
题目描述

   

    给定一个浮点数数组，任意取出数组中的若干个连续的数相乘，请找出其中乘积最大的子数组。例如，给定数组{−2.5, 4, 0, 3, 0.5, 8, −1}，则取出的最大乘积子数组为{3 , 0.5, 8}。也就是说，在上述数组中，3、0.5和8这三个数是连续的，而且乘积是最大的。

         

            以下代码仅仅是用sas iml实现蛮力解，熟悉一下iml解决问题对应的sas数据结构，后续会采用动态规划算法解。

关于IML的几点个人感觉：

1 有些矩阵(变量)要提前指定，感觉代码有点冗长

2 自带函数可以对于加减，元素位置方便计算，但是要算元素的连续乘积就没办法了

3 把行向量转变为方阵，很像特征根的值。最大的好处是少用了一个循环语句，我觉得程序里能少写一层循环实在是太好了。(虽然本质上还是做了循环，但是sas自带的效率应该更高)

另外，虽然iml有点像外挂，但是真的蛮好用，矩阵运算比数据集设置数组好多了。

SAS代码:

**********************************************************************

proc iml;/*a 原始数据*//*b 最大序列的开始位置，序列长度，最大乘积*//*c 对应的序列*/a={-2.5 4 0  3  0.5  8 -1};b={[3] 0};/*元素起始位置 及序列长度*/slen=ncol(a);tem=min(a);do i=1 to slen;   do j=1 to slen-i+1;   lpos=j+i-1;   sub=a[,j:lpos];   /*单位向量*/   ivec=i(ncol(sub));   /*转成方阵*/   sub1=t(sub)#ivec;   res=det(sub1);   if res >= tem then do;         b[1]=j;         b[2]=i;         b[3]=res;                 tem=res;         end;   end;end;c=a[,b[1]:b[1]+b[2]-1];print b;print c;quit;

结果：

   b    4         3        12  c 3       0.5       8

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏2 回帖

关键词：sas代码 动态规划 Andy 最大连续乘积子数组 Weixin 动态规划 sas代码 iml 最大连续乘积子数组

有空的时候也想学学IML，感觉用来解决某类问题很在行，尤其是那种自遍历的lookup
而且不知道以后在处理大数据的时候，会不会有可行性或效率提升的帮助

Tigflanker 发表于 2016-2-2 13:32
有空的时候也想学学IML，感觉用来解决某类问题很在行，尤其是那种自遍历的lookup
而且不知道以后在处理大数 ...

不用在base里定义和使用数组循环还是省很多事,而且很多算法都是基于矩阵运算的

mark一下:这部分是把子序列的数字转移到矩阵的主对角线上，然后利用det求行列式获得乘积。
因为在j递增的过程中维度是不断自增的，所以我用了ivec这个自增的单位矩阵。
do j=1 to slen-i+1;
   ipos=j+i-1;
   sub=a[,j:ipos];
   ivec=i(ncol(sub));
   sub1=t(sub)#ivec;
   res=det(sub1);