传智播客旗下技术交流社区北京校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 播妞 程序媛   /  2017-9-21 13:34  /  31754 人查看  /  1440 人回复  /   37 人收藏 转载请遵从CC协议 禁止商业使用本文

一. 算法
•        (一)经典的算法:
•        1.递归算法:
•        1)数据定义按递归定 义 fibonacci
•        2)问题揭发按递归解 决 回溯算法
•        3)数据结构按递归定 义 树遍历图搜索
•        经典题-整数划分:
1.jpg

(一)经典的算法:
•        2.分治算法:
•        对于规模为n的问题分解成k个规模小的问题他们彼此独立,然后再将 它们合并
•        分治策略的算法设计模式
•Divide_and_Conquer(P)
•        {
•if (|P|<=n0 ) return adhoc(P);
•divide P into smaller substances P1,P2,…,Pk;
•        for (i=1; i<=k; k++)
•yi=Divide-and-Conquer(Pi)        //递归解决Pi
•Return merge(y1,y2,…,yk)        //合并子问题
•        }

•        二分搜索:
•Public static int binarysearch(int[]data,intbeginindex,intendindex)
•Int beginindex=0;int endindex =n-1;
•While(beginindex<endindex)
•{ int mid =(beginindex+endindex)/2
•If(x==a[mid] return mid;
•If(x>a[mid] beginindex=mid+1;
•Else endindex=mid-1;}
•Return        -1
•        a[0:n-1] 找出
•        第k小的元素
•        快速排序算法
•        是分治算法的应
•        1.分析最优子结构:
•        2.重叠子问题;
•        题-最长公共子序列:
2.jpg

•        题-最大子段和:
•        B[j]=max{b[j-1]+a[j],a[j]}//条件b[i-j]>0 int MaxSum(int n)
[AppleScript] 纯文本查看 复制代码
{
int sum=0; int b=0;
for (int i=1;i<=n;i++)
{
if (b>0) b+=a; else b=a; if (b>sum) sum=b;
}
return sum;
int MaxSum(int n, int &besti, int &bestj)
{
int sum=0; int b=0;
int begin = 0;
for (int i=1;        i<=n;        i++)
{
if (b>0)        b+=a;
else {b=a;        begin = i;}
if (b>sum) //得到新的最优值时,更新最优解
{
sum = b; besti = begin; bestj = i;
}
}
return sum;
}


•        题0-1背包问题:
• 第一个式子是不装入物品i,也可能物品i无 法装入,背包的容量不变,转化为前i+1个 物品放与容量为j的背包中
•        第二个式子装入物品i则新增加价值vi,但容 量变位j-w,对于最后一个物品n,若j》=w
p(i,j)  max( p(i 1,j),p(i 1,j  wi )  vi }        j  wi
 p(i 1,j)        0   j  wi
•        题:最长单调子系列
• 辅助数组b表示以a为结尾的最长递增子 序列长度,则序列L的最长递增子序列的长 度:max {b}
•        B[1]=1;
•        B=max{b[k]}+1
int LIS_n2(int n)        //教材上这一句丢掉了
{
int b[NUM]={0};        //辅助数组b
int i,j; b[1] = 1;
int max = 0;        //数组b的最大值
for (i=2;i<=n; i++)
{
int k = 0;
for (j=1; j<i; j++)        //0~i-1之间,b的最大值
if (a[j]<=a && k<b[j]) k=b[j]; b = k+1;
if (max<b) max=b;
}
return max;
}
•        贪心选择性质是指所求问题的整体最优解可以通 过一系列局部最优的选择,即贪心选择来达到
Greedy(A)
{
S={ };        //初始解集合为空集
while (not solution(S))        //集合S没有构成问题的一个解
{
x = select(A);        //在候选集合A中做贪心选择
if feasible(S, x)        //判断集合S中加入x后的解是否
可行
S = S+{x};
A = A-{x};
}
return S;

(一)经典的算法:贪心算法背包
问题
double knapsack(int n, bag a[], double c)
{
double cleft = c; int i = 0;
double b = 0;
while(i<n && a.w<=cleft)
{
cleft -= a.w;
b += a.v;
//物品原先的序号是a.index,全部装入背包
a[a.index].x = 1.0; i++;
}
if (i<n)        {
a[a.index].x = 1.0*cleft/a.w;
b += a[a.index].x*a.v;
}
return b;
}
•        令cw(i)表示目前搜索到第i层已经装入背包的 物品总重量,即部分解(x1, x2 , …, xi)的重量:
i
cw(i)   x j wj
j1
•        对于左子树, xi =1 ,其约束函数为:
constraint (i)  cw(i  1)  wi
•        若constraint(i)>W,则停止搜索左子树,否
则继续搜索。
•        对于右子树,为了提高搜索效率,采用上界函数
Bound(i)剪枝。
•        令cv(i)表示目前到第i层结点已经装入背包的物品
价值:cv(i)   x jv j
j1

r(i) 

n
v j
ji1
•        令r(i)表示剩余物品的总价值:
Bound (i)

 cv(i) 

r(i)
•        则限界函数Bound(i)为:
#define NUM 100
int c;        //背包的容量
int n;        //物品的数量
int cw;        //当前重量
int cv;        //当前价值
int bestv;        //当前最优价值
//描述每个物品的数据结构 struct Object{
int w;        //物品的重量
int v;        //物品的价值
double d;        //物品的单位重量价值比
//物品的数组

void backtrack(int i)
{
//到达叶子结点时,更新最优值 if (i+1>n) {bestv = cv; return;}
//进入左子树搜索 if (cw+Q.w<=c)
{
cw += Q.w;
cv += Q.v; backtrack(i+1); cw -= Q.w;
cv -= Q.v;
}
//进入右子树搜索
if (Bound(i+1)>bestv) backtrack(i+1);

int cleft = c-cw;        //背包剩余的容量 int b = cv;                //上界
//尽量装满背包
while (i<n && Q.w<=cleft)
{
cleft -= Q.w;
b += Q.v; i++;
}
//剩余的部分空间也装满
if (i<n) b += 1.0*cleft*Q.v/Q.w; return b;
}
•        从活结点表中选择下一个活结点作为新的扩展 结点,分支限界算法通常可以分为两种形式:
1.FIFO(First In First Out)分支限界算法
–按照先进先出(FIFO)原则选择下一个活结点作为 扩展结点,即从活结点表中取出结点的顺序与加入结 点的顺序相同。
2.最小耗费或最大收益分支限界算法
–在这种情况下,每个结点都有一个耗费或收益。
–根据问题的需要,可能是要查找一个具有最小耗费 的解,或者是查找一个具有最大收益的解。
•        限界函数:
•        求max维护或节点,从活节点选择一个节点 作为扩展节点,对扩展节点的每个分支i, 计算其上界值,若当前最大的目标函数值 best不小于bound(i)不会放入活节点,否 则放入,所以若bound(i)《=best表示正 在搜索的节点i为死节点减掉
•        深度优先
•        广度优先 无回溯快
温馨提醒,文本格式略有错乱,建议大家回帖下载PDF版本,回帖即可下载附件,赶紧下载学习吧~

游客,如果您要查看本帖隐藏内容请回复


点评

mark,谢谢波妞.  发表于 2019-1-17 17:48
好  发表于 2018-12-22 23:58
优秀  发表于 2018-12-22 23:57
koko  发表于 2018-12-22 23:55
koko  发表于 2018-12-22 23:55
2323  发表于 2018-12-22 23:54
加一个0.0  发表于 2018-12-22 23:54
这个很需要  发表于 2018-12-22 23:53
如果有的话,那就美滋滋了  发表于 2018-11-19 15:47
为啥就是没有免费的下载呀  发表于 2018-11-19 15:45

评分

参与人数 8黑马币 +12 收起 理由
黑马雪鹏 + 1 淡定
DClear + 1 赞一个!
Joe0428 + 5 很给力!
追风12 + 1 赞一个!
qin_tiantian + 1 很给力!
星轩轩 + 1 很给力!
qq87438004 + 1 赞一个!
会哭的纸飞机 + 1 有才

查看全部评分

分享至 : QQ空间
收藏

1440 个回复

倒序浏览
回复 使用道具 举报 1 0
好好学习天天向上
回复 使用道具 举报 2 0
求面试题
回复 使用道具 举报
楼主好人
回复 使用道具 举报
好东西要分享
回复 使用道具 举报 1 0
吼哈  我来拿pdf     
回复 使用道具 举报 1 0
现在面试算法啥也不会了-_-||
来自宇宙超级黑马专属安卓客户端来自宇宙超级黑马专属安卓客户端
回复 使用道具 举报
休息休息休息休息休息休息下
回复 使用道具 举报 1 0
asdfasdasdfasd
回复 使用道具 举报
THANK YOU FENGXIANG
回复 使用道具 举报
谢谢谢谢
回复 使用道具 举报
求下载  求题
回复 使用道具 举报
谢谢谢谢侬
回复 使用道具 举报
很有用,值得学习,感谢楼主分享
回复 使用道具 举报
666666666
回复 使用道具 举报
求资源  求资源 求资源
回复 使用道具 举报
资源免费就好了
回复 使用道具 举报
好东西啊啊啊啊啊
回复 使用道具 举报
下载下来看看,感谢
回复 使用道具 举报 1 0
您需要登录后才可以回帖 登录 | 加入黑马