五大常用算法的经典问题？
[问题点数：40分，结帖人StudyTCPIP]
五大常用算法的经典问题？
[问题点数：40分，结帖人StudyTCPIP]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
2009年4月 Linux/Unix社区大版内专家分月排行榜第三
2013年6月 Linux/Unix社区大版内专家分月排行榜第二2013年5月 Linux/Unix社区大版内专家分月排行榜第二2013年3月 Linux/Unix社区大版内专家分月排行榜第二2013年1月 Linux/Unix社区大版内专家分月排行榜第二2012年12月 Linux/Unix社区大版内专家分月排行榜第二2012年8月 Linux/Unix社区大版内专家分月排行榜第二2011年12月 Linux/Unix社区大版内专家分月排行榜第二2011年10月 C/C++大版内专家分月排行榜第二2011年10月 Linux/Unix社区大版内专家分月排行榜第二
2012年6月 C/C++大版内专家分月排行榜第三2012年6月 PHP大版内专家分月排行榜第三2012年5月 C/C++大版内专家分月排行榜第三2012年3月 Linux/Unix社区大版内专家分月排行榜第三2012年2月 Linux/Unix社区大版内专家分月排行榜第三2011年11月 C/C++大版内专家分月排行榜第三
2009年4月 Linux/Unix社区大版内专家分月排行榜第三
2014年 总版技术专家分年内排行榜第二
2013年 总版技术专家分年内排行榜第三
2009年4月 Linux/Unix社区大版内专家分月排行榜第三
匿名用户不能发表回复！|豆丁微信公众号
君，已阅读到文档的结尾了呢~~
[试题]贪心算法经典例题
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
[试题]贪心算法经典例题
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口贪心算法经典例题_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
贪心算法经典例题
阅读已结束，下载本文需要
想免费下载更多文档？
定制HR最喜欢的简历
你可能喜欢五大常用算法二(贪心,分治) - 简书
五大常用算法二(贪心,分治)
贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解,如之前的,,。如果不要求绝对最佳答案,那么有时候我们使用简单的贪婪算法生成近似的答案.
贪心与动态规划
贪心算法和动态规划都需求最优子结构,但是贪心算法是自顶向下方式进行,就是每一步，根据策略得到一个当前最优解。传递到下一步，从而保证每一步都是选择当前最优的。最后得到结果.每一步的最优解都依赖上一部的最优解.你只考虑之前已做出的选择
而动态规划通常自底向上解各种子问题,每一步，根据策略得到一个更小规模的问题。最后解决最小规模的问题。得到整个问题最优解.全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解.你考虑的都是以后的子问题
经典的还是背包问题,之前的01背包问题我们采用动态规划解决而不能用贪心.但是如果改成部分背包问题呢:
假如有三件物品，背包可装50磅的物品，物品1重10磅，价值60元；物品2重20磅，价值100元；物品3重30磅，价值120元。你可以选择带走每个物品的全部或一部分，求如何选择可以使背包所装的价值最大？
注意到不同点是我们可以选择带走一部分,所以使用贪心算法十分自然地想到,先算含金量啊,先把含金量最高的都带完,再带含金量其次的...很容易得到解,带走一件1,一件2,2/3件3...比较简单代码不写.
活动安排问题
设有n个活动的集合E = {1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si & fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si &= fj或sj &= fi时，活动i与活动j相容.怎么尽可能地安排多的相容活动呢?
设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下:
注意要按结束时间的早晚排列,没排好的话,你可以回去用各种方法自己排.既然贪心么就是越早结束越好,给后面留尽可能多的空间.其次"目光短浅",从排列好的里一个个选,能选一个是一个,别管后面的...
显然,我们选择到了(1)1-4,(4)5-7,(8)8-11,(11)12-14
感觉不靠谱么,其实对于这个活动安排问题，贪心算法总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。
我们还是来代码:
package com.fredal.
import java.util.A
public class Arrange {
public static int[] greedyArrangement(int[] start,int[] end){
int total=start.
int endtime=end[0];//选择的所有活动的最末结束时间
int[] arrangement=new int[total];
arrangement[0]=1;//无脑选第一个 最早结束的那个
int count=1;
for(int i=0;i&i++){
if(start[i]&endtime){//下一个活动开始时间晚于当前活动结束时间
arrangement[count++]=i+1;//活动选中
endtime=end[i];//更新结束时间
public static void main(String[] args) {
int[] start={1,3,0,5,3,5,6,8,8,2,12};
int[] end={4,5,6,7,8,9,10,11,12,13,14};
int[] arrangement=greedyArrangement(start, end);
for(int i=0;i&arrangement.i++){
if(arrangement[i]!=0)
System.out.println("开始时间:"+start[arrangement[i]-1]+",结束时间:"+end[arrangement[i]-1]);
哈夫曼编码
哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同，如下表所示
我们可以求得对于标准编码位数需要(45+13+12+16+9+5)*3=300,而对于变长码45×1+13×3+12×3+16×3+9×4+5×4=224,压缩了很多...
首先要讲一讲前缀码:对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。
我们可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”.字符只放在树叶上,满二叉树是其基本特征,你知道放法太多了,所以关键问题变成了怎么寻找总价值最小的完全二叉树,即最优前缀码.
对于该例样本字母表的最优树如下b,位数正是224,图a不是完全二叉树显然不符合:
那么怎么寻找的呢,就是哈夫曼编码干的事了.构造过程如下:
假设编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树按顺序插入优先队列Q。经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T
代码实现,这里需要使用完全二叉树,发现之前写的没有特别符号要求的,就这里直接实现吧.还有优先队列类,用之前实现过的MyHeap,有需要可以查看.
package com.fredal.
public class Huffman {
static MyHeap&Node& heap=new MyHeap&Node&();//堆类
static class Node implements Comparable&Node&{
//权值 频率
private S//字符
private S//记录路径
priva//是否遍历过
public Node(int weight, String value) {
this.weight =
this.value =
public int compareTo(Node o) {
return weight-o.
public static Node bulidHuffman(Node[] nodes){
for(int i=0;i&nodes.i++){
heap.insert(nodes[i]);
while(heap.getCurrentSize()&1){
Node minA = heap.deleteMin();//弹出最小的两个
Node minB = heap.deleteMin();
Node sumNode=new Node(minA.weight+minB.weight,minA.value+minB.value);//权值和称为其父节点
//维护关系
sumNode.left=minA;
minA.path="0";//为了方便 直接把路径信息记这儿了
sumNode.right=minB;
minB.path="1";
minA.parent=sumN
minB.parent=sumN
heap.insert(sumNode);//插入堆
return heap.findMin();//返回最后一个
相当于是完整的树了
public static void printHuffman(Node node){
if(node.left!=null && !node.left.isvisited){//遍历左边
Node left = node.
left.isvisited=
printHuffman(left);
if(node.right!=null && !node.right.isvisited){//遍历右边
Node right=node.
right.isvisited=
printHuffman(right);
if(node.left==null && node.right==null){//是叶子节点
StringBuffer sb=new StringBuffer();
sb.append(node.path);
System.out.print(node.value+":");
while(node.parent!=null){
node=node.
if(node.path!=null)
sb.append(node.path);//访问父节点 获得路径信息
System.out.println(sb.reverse().toString());//输出
printHuffman(node);//递归 输出下一个叶子节点的编码
public static void main(String[] args) {
Node[] nodes={
new Node(45, "a"),
new Node(13, "b"),
new Node(12, "c"),
new Node(16, "d"),
new Node(9, "e"),
new Node(5, "f")
Node root = bulidHuffman(nodes);
printHuffman(root);
近似装箱问题
给定N 项物品，大小为 s1, s2, ..., sN，所有的大小都满足 0 & si & = 1 ；问题是要把这些物品装到最小数目的箱子中去， 已知每个箱子的容量是1个单位；下图显示的是对N项物品的最优装箱方法
这个问题有两种版本.第一种是联机装箱问题,必须将每一件物品放入一个箱子后才处理下一件物品.另外一种是脱机装箱问题,我们做任何事情都需要等到所有的输入数据被读取后才进行.
我们先来考虑联机装箱的三种算法,第一种是下项适合算法: 当处理任一物品时，我们检查看他是否还能装进刚刚装进物品的同一个箱子中去.如果能够装进去,那么就把它装入该箱子,否则,就开辟一个新箱子.例子如下:
我们用代码模拟:
package com.fredal.
import java.util.LinkedL
public class BinPacking {
static LinkedList&Box& boxes=new LinkedList&Box&();//存储所有箱子
static int index=1;
static class Box{//箱子类
p//剩余容量
private LinkedList&Double&
public Box(){
remain=1;//设容量初始为1
values=new LinkedList&Double&();//存储箱子中的物品
//下项适合算法
public static void nextfit(double[] a){
for(int i=0;i&a.i++){
if(boxes.peek()==null)
boxes.push(new Box());
Box last = boxes.peek();
if(last.remain&=a[i]){//装的下就装
last.values.add(a[i]);
last.remain-=a[i];
}else{//装不下就开辟新箱子
Box nbox=new Box();
nbox.values.add(a[i]);
nbox.remain-=a[i];
boxes.push(nbox);
show(boxes);
//输出显示
public static void show(LinkedList&Box& boxes){
while(!boxes.isEmpty()){
Box box = boxes.removeLast();
System.out.print("box"+index+++":");
while(!box.values.isEmpty()){
Double value = box.values.removeFirst();
System.out.print(value+" ");
System.out.println();
public static void main(String[] args) {
double[] a={0.2,0.5,0.4,0.7,0.1,0.3,0.8};
nextfit(a);
下项算法的性能是线性的,但是在实践中显然是不靠谱的.不需要开辟新箱子的时候开辟了新箱子.接下来讲首次适合算法:依序扫描这些箱子把新的一项物品放入足够盛下它的第一个箱子中.
代码如下,注意show()函数有点变化的:
package com.fredal.
import java.util.I
import java.util.LinkedL
public class BinPacking {
static LinkedList&Box& boxes=new LinkedList&Box&();//存储所有箱子
static int index=1;
static class Box{//箱子类
p//剩余容量
private LinkedList&Double&
public Box(){
remain=1;//设容量初始为1
values=new LinkedList&Double&();//存储箱子中的物品
//首次适合算法
public static void firstfit(double[] a){
for(int i=0;i&a.i++){
boolean flag=
if(boxes.peek()==null)
boxes.add(new Box());
Iterator&Box& it = boxes.iterator();
while(it.hasNext()){//从头到尾遍历 能装就装
Box box = it.next();
if(box.remain&=a[i]){
box.values.add(a[i]);
box.remain-=a[i];
if(!flag){//全部不能装就开辟新的
Box nbox=new Box();
nbox.values.add(a[i]);
nbox.remain-=a[i];
boxes.add(nbox);
show(boxes);
//输出显示
public static void show(LinkedList&Box& boxes){
while(!boxes.isEmpty()){
Box box = boxes.removeFirst();
System.out.print("box"+index+++":");
while(!box.values.isEmpty()){
Double value = box.values.removeFirst();
System.out.print(value+" ");
System.out.println();
public static void main(String[] args) {
double[] a={0.2,0.5,0.4,0.7,0.1,0.3,0.8};
firstfit(a);
第三个是最佳适合算法,该方法不是吧一项新物品放入所发现的第一个能够容纳它的箱子，而是放到所有箱子中能够容纳它的最满的箱子中.该算法对随记的输入表现的更好
代码如下,注意输出函数还是变了,并且采用了ArrayList存储:
package com.fredal.
import java.util.ArrayL
import java.util.I
import java.util.LinkedL
public class BinPacking {
static ArrayList&Box& boxes=new ArrayList&Box&();//存储所有箱子
static int index=1;
static class Box{//箱子类
p//剩余容量
private LinkedList&Double&
public Box(){
remain=1;//设容量初始为1
values=new LinkedList&Double&();//存储箱子中的物品
//最佳适合算法
public static void bestfit(double[] a){
for(int i=0;i&a.i++){
double remainMin=1+1;//最小的剩余容量 用于寻找最满的箱子 初始化表示比容量大1
int index=0;//记录箱子编号
if(boxes.size()==0)
boxes.add(new Box());
for(int j=0;j&boxes.size();j++){
Box box=boxes.get(j);
if(box.remain&=a[i] && box.remain&remainMin){//从头遍历 如果找到更满的并且能装下的就记录
remainMin=box.
if(remainMin&=1){//说明找到了可以装的
Box box = boxes.get(index);//装进记录好的最满的箱子
box.values.add(a[i]);
box.remain-=a[i];
}else{//找不到可以装的就开辟新的箱子
Box nbox=new Box();
nbox.values.add(a[i]);
nbox.remain-=a[i];
boxes.add(nbox);
show(boxes);
//输出显示
public static void show(ArrayList&Box& boxes){
for(int i=0;i&boxes.size();i++){
Box box=boxes.get(i);
System.out.print("box"+index+++":");
while(!box.values.isEmpty()){
Double value = box.values.removeFirst();
System.out.print(value+" ");
System.out.println();
public static void main(String[] args) {
double[] a={0.2,0.5,0.4,0.7,0.1,0.3,0.8};
bestfit(a);
接下来是脱机算法,显然脱机算法可以表现得更好.联机算法的问题在于在于将大项物品装箱困难,特别是当他们在输入的晚期出现的时候.于是脱机算法我们可以将各项物品排序，把最大的物品放在最先，此时我们可以应用首次适合算法或最佳适合算法，分别得到“首次适合递减算法”　和　”最佳适合递减算法”.
这两种算法是差不多的,我们以首次适合递减算法为例.
代码如下,我们使用快速排序.注意java中double数有些精度问题,上面的三个算法也会出现可能无法完全装满的问题,我就不去改了.这里改一下
package com.fredal.
import java.util.I
import java.util.LinkedL
public class BinPacking {
static LinkedList&Box& boxes=new LinkedList&Box&();//存储所有箱子
static int index=1;
static class Box{//箱子类
p//剩余容量
private LinkedList&Double&
public Box(){
remain=1;//设容量初始为1
values=new LinkedList&Double&();//存储箱子中的物品
//首次适合递减算法
public static void firstfit(double[] a){
quickSort(a, 0, a.length-1);
for(int i=0;i&a.i++){
boolean flag=
if(boxes.peek()==null)
boxes.add(new Box());
Iterator&Box& it = boxes.iterator();
while(it.hasNext()){//从头到尾遍历 能装就装
Box box = it.next();
if(box.remain&a[i]||Math.abs(box.remain-a[i])&Math.pow(10, -10)){//解决一下精度
box.values.add(a[i]);
box.remain-=a[i];
if(!flag){//全部不能装就开辟新的
Box nbox=new Box();
nbox.values.add(a[i]);
nbox.remain-=a[i];
boxes.add(nbox);
show(boxes);
//快速排序
public static void quickSort(double[] a,int left,int right){
if(left&right){//递归出口条件
int i=//左指针
int j=//右指针
double x=a[left];//选择第一个元素作为标尺
while(i&j){
while(i&j && a[j]&=x) j--;//从右向左找第一个大于x的数
if(i&j) a[i++]=a[j];
while(i&j && a[i]&x) i++;//从左向右找第一个小于等于x的数
if(i&j) a[j--]=a[i];
a[i]=x;//插入标尺
quickSort(a,left,i-1);//递归左边
quickSort(a, i+1, right);//递归右边
//输出显示
public static void show(LinkedList&Box& boxes){
while(!boxes.isEmpty()){
Box box = boxes.removeFirst();
System.out.print("box"+index+++":");
while(!box.values.isEmpty()){
Double value = box.values.removeFirst();
System.out.print(value+" ");
System.out.println();
public static void main(String[] args) {
double[] a={0.2,0.5,0.4,0.7,0.1,0.3,0.8};
firstfit(a);
分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础.
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法.
传统上,含有两个或以上的递归调用的叫做分治法.经典的例子就是,
接下来我们选一些其他的经典例子来分析
大整数乘法
设有两个大整数相乘,X=,Y=.那么XY=4047.易知我么的算法需要O(N?)即O(8?)次操作.
如果我们把X和Y都拆成两半,由最高几位和最低几位组成.那么XL=6143,XR=8521,YL=9473,YR=6470.于是X=XL*10^4+XR,Y=YL*10^4+YR.可以得到
XY=XL*YL*10^8+(XL*YR+XR*YL)*10^4+XRYR
显然这个式子就是由4个乘法组成的,每一个都是原问题的一半,而108,104的乘法只是添一些0,于是可以得到递归:T(N)=4T(N/2)+O(N)..
我们按照主定理(相关资料查阅维基百科),可以求得算法复杂度仍然是O(N?).并没有改进这个问题.
观察XL*YR+XR*YL,可以分解为(XL-XR)(YR-YL)+XL*YL+XR*YR,我们仅需要算前面一项,后面的两项已经计算过了.于是得到了T(N)=3T(N/2)+O(N).,按照主定理,可得T(N)=O(N^1.59).当然对于每一个乘积我们还可以继续递归下去,一般到四位数就不用递归了.
我们还是采取代码来模拟过程:
package com.fredal.
public class BigMultiply {
//大整数相乘
public static String multiply(String x,String y){
int flag1=0;//x的符号位
int flag2=0;//y的符号位
if(x.charAt(0)=='-'){//处理符号
x=x.substring(1);//先把符号位截掉
if(y.charAt(0)=='-'){
y=y.substring(1);
String flag=(flag1^flag2)==1?"-":"";//相乘即异或之后符号位
if(x.length()&y.length())//保证x的位数更大
return flag+multiply(y, x);
if(x.length()&=4)
return flag+Integer.parseInt(x)*Integer.parseInt(y);//少于等于四位数直接计算了
if(x.length()%2==0){//x位数是偶数 就把y补成和x一样长
while(x.length()&y.length())
}else{//x位数不是偶数 就先把x补成偶数 再把y补成和x一样长
while(x.length()&y.length())
String xl=x.substring(0,x.length()/2);
String xr=x.substring(x.length()/2);
String yl=y.substring(0,y.length()/2);
String yr=y.substring(y.length()/2);
String D1=minus(xl, xr);//xl-xr
String D2=minus(yr, yl);//yr-yl
String xlyl=multiply(xl, yl);//xl*yl
String xryr=multiply(xr, yr);//xr*yr
String D3=add(multiply(D1, D2)+"", add(xlyl, xryr));//D1*D2+Xl*Yl+Xr*Yr
return flag+add(shift(xlyl, x.length()),add(shift(D3, x.length()/2),xryr));//Xl*Yl*10^n+D3*10^(n/2)+Xr*Yr
//大数相减 带符号处理
public static String minus(String x,String y){
int large=compare(x, y);
String flag=large&=0?"":"-";//加上符号
if (large==0)
return "0";
else if(large&0)//转化成大的减小的
return minusBigNum(x,y);
return flag+minusBigNum(y,x);
//大数相减
private static String minusBigNum(String x,String y){//大数减小数
int len=x.length();
while(len&y.length())
StringBuilder result=new StringBuilder();
int flag=0;//表示是否进位
for(int i=len-1;i&=0;i--){
int xs=Integer.parseInt(String.valueOf(x.charAt(i)));
int ys=Integer.parseInt(String.valueOf(y.charAt(i)));
if(xs+flag&=ys){//别忘了把flag加上
result.append(xs-ys+flag);
result.append(10+xs-ys+flag);
return clearZero(result.reverse().toString());
//大数相加
public static String add(String x,String y){
if(x.charAt(0)=='-'){//先处理符号
x=x.substring(1);
if(y.charAt(0)=='-'){
y=y.substring(1);
return "-"+add(x,y);
return minus(y, x);
if(y.charAt(0)=='-'){
y=y.substring(1);
return minus(x, y);
if(x.length()&y.length())
return add(y, x);//保证x的位数更大
int len=x.length();
while(len&y.length())//补位使位数相等
StringBuilder result=new StringBuilder();
int flag=0;//表示是否进位
for(int i=len-1;i&=0;i--){
int xs=Integer.parseInt(String.valueOf(x.charAt(i)));
int ys=Integer.parseInt(String.valueOf(y.charAt(i)));
if(xs+ys+flag&9){//别忘了把flag加上
result.append(xs+ys-10+flag);
result.append(xs+ys+flag);
if(flag!=0)
result.append(1);
return clearZero(result.reverse().toString());
//计算10n次方的 就是后面加0
public static String shift(String x,int n){
for(int i=0;i&n;i++){
private static String clearZero(String str){
while(i&str.length()&&str.charAt(i)=='0'){
return str.substring(i);
//比较两个数的大小
private static int compare(String x,String y){
if(x.length()&y.length())
else if(x.length()&y.length())
return -1;
int index = 0;
while (index & x.length() && x.charAt(index) == y.charAt(index))
if (index == x.length())
return x.charAt(index) & y.charAt(index)? 1 : -1;
public static void main(String[] args) {
System.out.println(multiply("-", ""));
System.out.println(multiply("-1",
"-5699"));
算法并不复杂,但是处理符号什么的还是比较麻烦的,而且加法减法啥的都要自己去实现.
Strassen矩阵乘法
两个矩阵的乘法学过线性代数的都知道怎么求,一般来说复杂度为O(N^3).直接给出标准的算法
package com.fredal.
public class MartixMultiply {
public static int[][] multiply(int[][] a, int[][] b) {
int n = a.
int[][] c = new int[n][n];
for (int i = 0; i & i++)
for (int j = 0; j & j++)
c[i][j] = 0;
for (int i = 0; i & i++)
for (int j = 0; j & j++)
for (int k = 0; k & k++)
c[i][j] += a[i][k] * b[k][j];
public static void main(String[] args) {
int[][] a = { { 1, 2 }, { 3, 4 } };
int[][] b = { { 3, 4 }, { 7, 2 } };
int[][] c = multiply(a, b);
System.out.println(c[0][0] + " " + c[0][1] + " " + c[1][0] + " "
+ c[1][1]);
Strassen提出了算法打破了O(N^3)的屏障.用到分治算法,把矩阵分为4块.
可以得到递推关系T(N)=7T(N/2)+O(N?),依据主定理得到解T(N)=O(N^2.81).
这儿不做出证明,显然这用到了分治法的思想,我们用代码模拟
package com.fredal.
public class MartixMultiply {
public static int[][] StrassenMultiply(int[][] a, int[][] b) {
int[][] result = new int[a.length][b.length];
if (a.length == 2)
return multiply(a, b);// 如果是2阶的 就结束递归 用传统方法
// a的四个子矩阵
int[][] A00 = divide(a, 1);
int[][] A01 = divide(a, 2);
int[][] A10 = divide(a, 3);
int[][] A11 = divide(a, 4);
// b的四个子矩阵
int[][] B00 = divide(b, 1);
int[][] B01 = divide(b, 2);
int[][] B10 = divide(b, 3);
int[][] B11 = divide(b, 4);
int[][] m1 = StrassenMultiply(addArrays(A00, A11), addArrays(B00, B11));
int[][] m2 = StrassenMultiply(addArrays(A10, A11), B00);
int[][] m3 = StrassenMultiply(A00, subArrays(B01, B11));
int[][] m4 = StrassenMultiply(A11, subArrays(B10, B00));
int[][] m5 = StrassenMultiply(addArrays(A00, A01), B11);
int[][] m6 = StrassenMultiply(subArrays(A10, A00), addArrays(B00, B01));
int[][] m7 = StrassenMultiply(subArrays(A01, A11), addArrays(B10, B11));
int[][] C00 = addArrays(m7, subArrays(addArrays(m1, m4), m5));// m1+m4-m5+m7
int[][] C01 = addArrays(m3, m5); // m3+m5
int[][] C10 = addArrays(m2, m4); // m2+m4
int[][] C11 = addArrays(m6, subArrays(addArrays(m1, m3), m2));// m1+m3-m2+m6
// 将四个矩阵合并起来
Merge(result, C00, 1);
Merge(result, C01, 2);
Merge(result, C10, 3);
Merge(result, C11, 4);
// /分割得到子矩阵
private static int[][] divide(int[][] a, int flag) {
int[][] result = new int[a.length / 2][a.length / 2];
switch (flag) {
for (int i = 0; i & a.length / 2; i++)
for (int j = 0; j & a.length / 2; j++)
result[i][j] = a[i][j];
for (int i = 0; i & a.length / 2; i++)
for (int j = a.length / 2; j & a. j++)
result[i][j - a.length / 2] = a[i][j];
for (int i = a.length / 2; i & a. i++)
for (int j = 0; j & a.length / 2; j++)
result[i - a.length / 2][j] = a[i][j];
for (int i = a.length / 2; i & a. i++)
for (int j = a.length / 2; j & a. j++)
result[i - a.length / 2][j - a.length / 2] = a[i][j];
// 矩阵加法
private static int[][] addArrays(int[][] a, int[][] b) {
int[][] result = new int[a.length][a.length];
for (int i = 0; i & result. i++) {
for (int j = 0; j & result. j++) {
result[i][j] = a[i][j] + b[i][j];
// 矩阵减法
private static int[][] subArrays(int[][] a, int[][] b) {
int[][] result = new int[a.length][a.length];
for (int i = 0; i & result. i++) {
for (int j = 0; j & result. j++) {
result[i][j] = a[i][j] - b[i][j];
// 将b复制到a的指定位置
private static void Merge(int[][] a, int[][] b, int flag) {
switch (flag) {
for (int i = 0; i & a.length / 2; i++)
for (int j = 0; j & a.length / 2; j++)
a[i][j] = b[i][j];
for (int i = 0; i & a.length / 2; i++)
for (int j = a.length / 2; j & a. j++)
a[i][j] = b[i][j - a.length / 2];
for (int i = a.length / 2; i & a. i++)
for (int j = 0; j & a.length / 2; j++)
a[i][j] = b[i - a.length / 2][j];
for (int i = a.length / 2; i & a. i++)
for (int j = a.length / 2; j & a. j++)
a[i][j] = b[i - a.length / 2][j - a.length / 2];
// 常规做法
public static int[][] multiply(int[][] a, int[][] b) {
int n = a.
int[][] c = new int[n][n];
for (int i = 0; i & i++)
// Initialization
for (int j = 0; j & j++)
c[i][j] = 0;
for (int i = 0; i & i++)
for (int j = 0; j & j++)
for (int k = 0; k & k++)
c[i][j] += a[i][k] * b[k][j];
public static void main(String[] args) {
int[][] a = { { 1, 2, 6, 7 }, { 3, 4, 5, 4 }, { 5, 8, 3, 8 },
{ -6, 4, 3, 9 } };
int[][] b = { { 3, 4, 9, 0 }, { 7, 2, -5, -6 }, { 0, 7, -4, 6 },
{ -6, 3, -5, 4 } };
int[][] c = multiply(a, b);
System.out.println(c[0][0] + " " + c[0][1] + " " + c[1][0] + " "
+ c[1][1]);
最近点对问题
这个问题真的很有意思,给定空间上的n个节点S={(xi,yi)}，如何查找这n个点对中最近的点对的距离?
我们都知道两点间距离:((xi-xj)?+(yi-yj)?)1/2
那么如果使用暴力搜索,需要两两检测,需要花费O(N?).
我们可以采用分治法的思想.首先我们假设这些点都已经按照x坐标排序过,那么可以在中间画一条线,把点集分为Pl和Pr,那么最近的一对点要么都在Pl中,要么都在Pr中,要么分别在Pl和pr中,把这三个距离分别用dl,dr,dc表示.
显然我们可以递归第计算dl和dr,关键是计算dc.令δ=min(dl,dr),显然我们可以做出双道带,来缩小考虑的范围
对于在带中的,我们可以通过两层循环蛮力计算,但毕竟还是不好,最坏的情况是说有点都可能在这带状区域里.那么考虑对y坐标排序.如果pi和pj的y坐标差大于δ,那么可以直接break跳出内循环.如对于p3来说,我们只需要考虑p4和p5,之后的break就行了.
还有一点可优化的是,其实对于任意的点pi,最多有7个点需要被考虑.
如图所示,这是点最多的情况.因为如果在上图的情况中随便再添一个点,比如在左边,那么这个点距离左边其他四个点的距离肯定有小于δ的(最均匀矩形中心,距离小于δ).那么只要距离一个点小于δ.那么与之前的假设在Pl中最短的距离为δ矛盾了!所以我们只需考虑最坏情况,某个角上是pi,那么其余还有7个点要考虑,得证.
接下来就容易了,但是还有要注意的是,不能每次递归都去排序x,y坐标.可以保留两个表,一个x坐标排序的表,一个y坐标排序的表.这个算法是O(NlogN)的.
还是来实现吧:
package com.fredal.
import java.util.ArrayL
import java.util.S
import java.util.TreeS
public class Distance {
static final int NUM=10;//使用穷举法的点数
public static void main(String[] args) {
Set&Point& testData = new TreeSet&Point&();
java.util.Random random = new java.util.Random();
for(int i = 0;i & 100000;i++){
int x = random.nextInt(100000);
int y = random.nextInt(100000);
testData.add(new Point(x, y));
Point [] points = new Point[testData.size()];
points = (Point[]) testData.toArray(points);
Point[] result=new Point[2];
long startTime=System.currentTimeMillis();
//获取开始时间
result=findpair(points);
long endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("最近点: ("+result[0].getX()+","+result[0].getY()
+")--("+result[1].getX()+","+result[1].getY()+")");
System.out.println("距离为: "+distance(result[0], result[1]));
System.out.println("分治法运行时间:"+(endTime-startTime)+"ms");
long startTime2=System.currentTimeMillis();
//获取开始时间
result=bong(points);
long endTime2=System.currentTimeMillis(); //获取结束时间
System.out.println("穷举法运行时间:"+(endTime2-startTime2)+"ms");
//寻找最近点对
public static Point[] findpair(Point[] p){
Point[] result=new Point[2];
if(p.length&NUM)
return bong(p);
//开始画线了
求所有点在x坐标的中位数
int minX = (int) Double.POSITIVE_INFINITY;
int maxX = (int) Double.NEGATIVE_INFINITY;
for(int i = 0; i & p. i++){
if(p[i].getX() & minX)
minX = (int) p[i].getX();
if(p[i].getX() & maxX)
maxX = (int) p[i].getX();
int midX = (minX + maxX)/2;
//把以midx为界划分出的点分成两组放到两个表
ArrayList&Point& L1=new ArrayList&Point&();
ArrayList&Point& L2=new ArrayList&Point&();
for(int i = 0; i & p. i++){
if(p[i].getX() &= midX)
L1.add(p[i]);
if(p[i].getX() & midX)
L2.add(p[i]);
//按x坐标排序
Point [] p1 = new Point[L1.size()];
Point [] p2 = new Point[L2.size()];
L1.toArray(p1);
L2.toArray(p2);
mergeSort(p1, "x");
//按X坐标升序排列
mergeSort(p2, "x");
//按X坐标升序排列
//递归求p1,p2中最近的两个点
Point[] result1 = new Point[2];
result1 = findpair(p1);
Point[] result2 = new Point[2];
result2 = findpair(p2);
//求二者中的最小值
if (distance(result1[0], result1[1])&distance(result2[0], result2[1])) {
result=result1;
result=result2;
double distance=Math.min(distance(result1[0], result1[1]),distance(result2[0], result2[1]));
//开始划分带了
在两个子集中找哪些距离划分线小于d的保存
ArrayList&Point& L3 = new ArrayList&Point&();
for(int i = 0; i & p1. i++){
if(midX - p1[i].getX() & distance)
L3.add(p1[i]);
for(int i = 0; i & p2. i++){
if(p2[i].getX() - midX & distance){
L3.add(p2[i]);
//将得到的按照y升序排列
Point [] p3 = new Point [L3.size()];
L3.toArray(p3);
mergeSort(p3, "y");
//然后开始优化的穷举 即比较之后的7个点
if (p3.length&NUM) {
Point[] temp= bong(p3);
if (distance(temp[0], temp[1])&distance&&distance(temp[0], temp[1])!=0) {
for(int i=0;i&p3.length-7;i++){
for(int j=1;j&8;j++){
if (i+j&=p3.length) {
tempd=distance(p3[i], p3[i+j]);
if (tempd&distance&tempd!=0) {
result[0]=p3[i];
result[1]=p3[i+j];
//归并排序
private static void mergeSort(Point[] p, String flag) {
Point[] result = new Point[p.length];
mergeSort(p, result, 0, p.length - 1, flag);
private static void mergeSort(Point[] a, Point [] result, int left, int right, String flag){
if(left & right){
int center = (left + right) && 1;
mergeSort(a, result, left, center, flag);
mergeSort(a, result, center + 1, right, flag);
merge(a, result, left, center + 1, right, flag);
private static void merge(Point [] a, Point [] result, int leftPos, int rightPos, int rightEnd, String flag){
int leftEnd = rightPos - 1;
int numOfElements = rightEnd - leftPos + 1;
int tmpPos = leftP
//游标变量, 另两个游标变量分别是leftPos 和 rightPos
while(leftPos &= leftEnd && rightPos &= rightEnd){
if(flag.equals("x")){
if(a[leftPos].getX() &= a[rightPos].getX())
result[tmpPos++] = a[leftPos++];
result[tmpPos++] = a[rightPos++];
}else if(flag.equals("y")){
if(a[leftPos].getY() &= a[rightPos].getY())
result[tmpPos++] = a[leftPos++];
result[tmpPos++] = a[rightPos++];
throw new RuntimeException();
while(leftPos &= leftEnd)
result[tmpPos++] = a[leftPos++];
while(rightPos &= rightEnd)
result[tmpPos++] = a[rightPos++];
//将排好序的段落拷贝到原数组中
System.arraycopy(result, rightEnd-numOfElements+1, a, rightEnd-numOfElements+1, numOfElements);
private static Point[] bong(Point[] p){
Point[] result=new Point[2];
if (p.length&=1) {
result[0]=new Point(Double.MIN_VALUE, Double.MIN_VALUE);
result[1]=new Point(Double.MAX_VALUE, Double.MAX_VALUE);
double min=distance(p[0], p[1]);
int start=0;
int end=1;
for (int i = 0; i & p. i++) {
for (int j = i+1; j & p. j++) {
if (distance(p[i], p[j])&min&&distance(p[i], p[j])!=0) {
min=distance(p[i], p[j]);
result[0]=p[start];
result[1]=p[end];
//计算距离
private static double distance(Point p1,Point p2){
return Math.sqrt((p1.getX()-p2.getX())*(p1.getX()-p2.getX())+(p1.getY()-p2.getY())*(p1.getY()-p2.getY()));
//用一个类来表示点
static class Point implements
Cloneable,Comparable&Point&{
double x,y;
public Point(double x, double y) {
public double getX() {
public double getY() {
public int compareTo(Point o) {
if(x == o.getX() && y == o.getY())
public boolean equals(Object p) {
// TODO 自动生成的方法存根
if (this.x==((Point) p).getX()&&this.y==((Point) p).getY()) {
我们采用了随机数产生器随机产生点,并统计了分治法与纯粹暴力搜索的运行时间,差距相当明显(这个程序当规模特别大的时候还是会栈溢出,为啥)
泊松分酒问题
讲这道题纯粹就是比较好玩,就记录一下.泊松分酒是很著名的一道题,讲的是假设某人有12品脱的啤酒一瓶，想从中倒出六品脱，但是恰巧身边没有6品脱的容器，仅有一个8品脱和一个5品脱的容器，怎样倒才能将啤酒分为两个6品脱呢？
我们用代码模拟很简单的就得到了答案
package com.fredal. import java.util.HashS
import java.util.LinkedL
import java.util.S
public class Oil {
static class Status{
static int[] full={12,8,5};//满的状态
int[] bottle=new int[3];//瓶子的状态
S//从哪个状态来的
public Status(int a,int b,int c){
bottle[0]=a;
bottle[1]=b;
bottle[2]=c;
//获取某种状态开始下一步的所有的状态
public Set opreation(){
Set res=new HashSet();
//开始倒酒
for(int i=0;i&bottle.i++){
for(int j=0;j&bottle.j++){
if(i==j) //不倒自己
if(bottle[i]==0)//自己是空的 不倒
if(bottle[j]==full[j])//对方是满的 不倒
Status t=new Status(bottle[0], bottle[1], bottle[2]);
t.from=//从自己这个状态开始变化
//真的开始倒酒了
t.bottle[j]+=t.bottle[i];
t.bottle[i]=0;
if(t.bottle[j]&full[j]){//装不下了
t.bottle[i]=t.bottle[j]-full[j];//满的倒回去
t.bottle[j]=full[j];
res.add(t);
//是否含有某种状态
public boolean has2(int x){
int index=0;
if (bottle[0]==x) index++;
if (bottle[1]==x) index++;
if (bottle[2]==x) index++;
return index==2?true:
public Status getFrom() {
public String toString(){
return "&" + bottle[0] + "," + bottle[1] + "," + bottle[2] + "&";
public int hashCode() {
return 100;
public boolean equals(Object obj) {
Status x=(Status)
return bottle[0]==x.bottle[0]&&bottle[1]==x.bottle[1]&&bottle[2]==x.bottle[2];
public static void main(String[] args) {
Set&Status& all=new HashSet&Status&();//存放所有结果状态
all.add(new Status(12, 0, 0));
Set newset=new HashSet();
for(Status x:all){//所有上一种状态产生所有下一种状态
Set t = x.opreation();
newset.addAll(t);
if(all.containsAll(newset))//出口
all.addAll(newset);
LinkedList&Status& list=new LinkedList&Status&();//存放有6的一溜
for(Status k:all){
if(k.has2(6)){
while(k!=null){
list.push(k);
k=k.getFrom();//从终止状态开始往上追溯
while(!list.isEmpty()){
System.out.println(list.pop());
这个解法找到的其实是最优解,至于为什么呢,其实利用set的方法十分巧妙,结果集set里随着一次次的分酒一次次地扩增,当第一次出现含有两个6的状态的时候,再往前追溯,步骤是最少的!因为这个我们想要的状态是第一次出现.
假如我们每次都打印出all集合,可以知道,当第一次找到含有两个6状态的时候程序并没有结束,因为还没有找到所有的状态.
而后面的状态再进行分酒时,仍有可能产生两个6的状态,但是想要加入set集合的时候就行不通了,所以此程序只输出最早加入的那一个解,并且是最优的.
当然这种算法并不能输出所有的解,如果要得到所有的解,我们可以采用以下算法,这种算法借鉴了图的深度搜索(DFS)以及回溯的技巧,需要注意的是,和8皇后问题一样,需要回溯的时机有两个,出错的时候和找到某一组解的时候.
package com.fredal.
import java.util.ArrayL
import java.util.L
import java.util.S
public class Oil {
int[] full = new int[3]; //满状态 容量
int[] bottle = new int[3]; //瓶子的状态
int target = 0; //目标
List&int[]& res = new ArrayList&int[]&();//存放结果
public void opreation(int[] bottle) {
for(int i=0;i&3;i++) {
for(int j=1;j&3;j++){//每个瓶子都不往自己倒 总共6种可能性
int[] temp = bottle.clone();//每次循环都创建临时数组
int to=(i+j)%3;//(i+j)%3 是除每种i瓶子外其他两个瓶子的序号,即要倒的目标
if(temp[i]==0)//自己是空的 不倒
if(temp[to]==full[to])//对方是满的 不倒
//开始倒酒
temp[to]+=temp[i];
temp[i]=0;
if(temp[to]&full[to]){//装不下了
temp[i]=temp[to]-full[to];//满出来的部分倒回去
temp[to]=full[to];
if(had(temp))//检测是否已经存在相同状态,防止重复
res.add(temp);//添加到结果链表
if(has2(temp))//如果找到有两个想要的状态的结果就返回
opreation(temp);//继续下一次分酒
res.remove(res.size()-1); //回溯 仔细体会
//是否以及含有状态
private boolean had(int[] bottlex) {
for(int[] e:res)
if(e[0]==bottlex[0]&&e[1]==bottlex[1]&&e[2]==bottlex[2])
//检测找到结果
private boolean has2(int[] bottle) {
int index=0;
for(int i=0;i&bottle.i++)
if(bottle[i]==target) index++;
if(index==2){
show(res);//输出
res.remove(res.size()-1);//回溯
private void show(List&int[]& res) {
for(int[] e:res) {
System.out.println(e[0] + "," + e[1] + "," + e[2]);
System.out.println();
public static void main(String[] args) {
Oil o = new Oil();
Scanner scanner = new Scanner(System.in);
String s ="";
if(scanner.hasNext()) {
s = scanner.nextLine();
String[] data = s.split(",");
int[] d = new int[data.length];
for(int i=0;i&data.i++){
d[i] = Integer.parseInt(data[i]);
o.full = new int[]{d[0],d[1],d[2]};
o.bottle = new int[]{d[3],d[4],d[5]};
o.target = d[6];
o.res.add(new int[]{d[3],d[4],d[5]});//添加初始状态
o.opreation(o.bottle);
显然,按照深度搜索并不能有效地找到最优解.上面两种算法都是比较巧的,我也比较喜欢.
如果要同时找到所有解和最优解,用图的广度搜索(BFS)会很方便,这也是网上采用的最多的,代码到处都有,就不写了.
更多内容与相关下载请查看扩展阅读
我就是我的作品
回溯算法 回溯法：也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因为当目前的可能答案被测试出不可能可以获得最终解时，则撤销当前的这一步求解过程...
背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪：刷leetcode是什么样的体验？ 慢慢有一些赞和感谢, 备受鼓舞, 于是我把所做过的题目用一个script跑了一下，编辑成一篇文章。这个总结页面是这么规划的： 题目名称(答案...
【程序1】 题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ //这是一个菲波拉契数列问题 publicclass lianxi01 { public static void...
Java经典问题算法大全 /*【程序1】 题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ 1.程序分析： 兔子的规律为数列1,1,2,3,5,8,13,21.... */ ...
1. Java基础部分 基础部分的顺序：基本语法，类相关的语法，内部类的语法，继承相关的语法，异常的语法，线程的语法，集合的语法，io的语法，虚拟机方面的语法。 1、一个&.java&源文件中是否可以包括多个类（不是内部类）？有什么限制？ 可以有多个类，但只能有一个publ...
环境都拍照很重要。 而构图，模特穿着表达也很重要。更重要的是，摄影师将这几点融合起来！ 谢谢大家，欢迎交流。
一，培养孩子不需要我们教 孩子画画要我们交吗?成人的教会给孩子一个框框。牢牢的束缚住孩子的思维，钳住孩子的想象，翅膀。我们不教孩子怎么会呀？首先我们需要创造一个有准备的环境，这个环境应该自由宽松，符合孩子的年龄特点，家长要善于发现孩子的兴趣所在，简单的说就是让孩子在适合的时...
琳常自夸自己性格好，人缘好，我们挤兑她长得太随和，没有攻击性，结果最逗的是原来在一起工作还不错的同事，忽然就不理她了，她百思不得其解，气呼呼的问，为什么呀？为什么呀？我没有得罪她呀。我们说大概觉得你没有利用价值了，以前有的时候就理你呗。 琳怀孕后，经常担心孩子肤色，我们也默...
导语：随着大数据的发展，现在出现的列式存储和列式数据库,如Hbase。它与传统的行式数据库有很大区别的。 定义 行式数据库是按照行存储的，行式数据库擅长随机读操作不适合用于大数据。像SQL server,Oracle，mysql等传统的是属于行式数据库范畴。 列式数据库从一...
它望着人群中每个人的脸都是倒立的冲着它善意的微笑着，路过的人冲着它善意的微笑，有人冲着它有人递给它一块生鱼片，它开心的吃着，嘴巴里面时不时冒出奇怪喵喵喵的声音…这是幸福的满足的声音。
有人又给它一个气球，一阵风吹过，它一个箭步抓着气球乱跑，小爪子试探性的抓了一下，又...