首页 > 代码库 > Runnable接口和贪心算法

Runnable接口和贪心算法

1 Runnable接口

Runnable 接口应该由那些打算通过某一线程执行其实例的类来实现。设计该接口的目的是为希望在活动时执行代码的对象提供一个公共协议。激活的意思是说某个线程已启动并且尚未停止。

在java中可有两种方式实现多线程,一种是继承Thread类,一种是实现Runnable接口。实际上,Thread实现了Runnable接口。

2 贪心算法

贪心算法把问题分解为几个有顺序的子问题,逐一对子问题进行求解,每一步都是在已求解子问题的基础上求取最优解,是对已求解部分解的一个扩展,直到获得问题的完整解。

贪心算法的解对其每一个子问题都是最优解,但对全局来讲,一般只是局部最优解。除非

  • 子问题互相独立。这样问题就变为分治法的问题。
  • 最优子结构。其意义是局部最优解能决定全局最优解。

如果不满足以上条件,贪心算法至少是一种非常高效的算法,并且得到的次优解,一般足以应付工程需要。