贪心算法的定义：
贪心算法在对问题求解时，总是做出在当前看来是最好的选择。不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法的举例
有十一个快件，每个快件有送货的起始时间，要求用最少的车，运送完所有的快件。
快件1:1:00-4:00
快件2:3:00-5:00
快件3:0:00-6:00
快件4:5:00-7:00
快件5:3:00-8:00
快件6:5:00-9:00
快件7:6:00-10:00
快件8:8:00-11:00
快件9:8:00-12:00
快件10:2:00-13:00
快件11:12:00-14:00
分析:要使用最少的车运送,那么在同一辆车上的派件必须是第二个派件的开始派发时间大于第一个
派件的截至派发时间，利用贪心算法(从局部选取最优解)那么就可以解决此问题
代码
Car类
import java.util.List;
/**
* 封装的是该车可以保存的派件信息
*/
public class Car
{
private List<Goods> goodsList;
public List<Goods> getGoodsList()
{
return goodsList;
}
public void setGoodsList(List<Goods> goodsList)
{
this.goodsList = goodsList;
}
@Override
public String toString()
{
String value="";
for (Goods goods : goodsList)
{
value+=goods.toString();
}
return value;
}
}
Goods类
/**
* 封装的是派件的一些相关信息
*/
public class Goods
{
private String name;
private int startTime;
private int endTime;
public int getStartTime()
{
return startTime;
}
public void setStartTime(int startTime)
{
this.startTime = startTime;
}
public int getEndTime()
{
return endTime;
}
public void setEndTime(int endTime)
{
this.endTime = endTime;
}
public String getName()
{
return name;
}
public Goods(String name, int startTime, int endTime)
{
this.name = name;
this.startTime = startTime;
this.endTime = endTime;
}
@Override
public String toString()
{
return name+" ";
}
}
GoodsSort类
import java.util.Comparator;
/**
* 以派件的截至时间进行排序
*/
public class GoodsSort implements Comparator<Goods>
{
@Override
public int compare(Goods g0, Goods g1)
{
return g0.getEndTime()-g1.getEndTime();
}
}
ArrangeCar类用于安排车辆
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
public class ArrangeCar
{
private static List<Car> cars=new ArrayList<>();
public static void main(String[] args)
{
List<Goods> goodsList = addGoods();
System.out.println("排序前");
printGoods(goodsList);
//对派件进行排序以派件的endTime进行排序
Collections.sort(goodsList, new GoodsSort());
System.out.println('\n'+"排序后");
printGoods(goodsList);
System.out.println();
greedySelect(goodsList);
System.out.println("共有"+cars.size()+"种派件方案");
for (Car car : cars)
{
System.out.println(car);
}
}
/**
* 贪心算法的运用
* @param goodsList
*/
public static void greedySelect(List<Goods> goodsList)
{
Goods goods=goodsList.remove(0);//获取排好序之后的第一个派件
int firstEndTime=goods.getEndTime();//得到派件的endTime
Car car=new Car();//新建立一个Car对象用于装载派件对象
List<Goods> gList=new ArrayList<>();
gList.add(goods);
car.setGoodsList(gList);
cars.add(car);//cars用于记录用了多少辆车
for(Iterator<Goods> iterator=goodsList.iterator();iterator.hasNext();)
{
Goods otherGoods=iterator.next();
//循环取出派件队列里面的派件，获得其开始派发时间同第一个派件的截至派发时间进行比较
//如果后面派件的开始派发时间大于第一个的派发时间那么可以用这两个派件装在一辆车上面
if(firstEndTime<=otherGoods.getStartTime())
{
gList.add(otherGoods);//装在同一辆车上面
firstEndTime=otherGoods.getEndTime();//改变截至派发时间值
iterator.remove();//移除该派件
}
}
//当循环完之后还有派件那么就进行递归再次装载车辆
if(goodsList.size()!=0)
{
greedySelect(goodsList);
}
}
/**
* 添加派件
* @return
*/
public static List<Goods> addGoods()
{
List<Goods> goodsList=new ArrayList<>();
Goods thing8 = new Goods("派件8", 8, 11);
goodsList.add(thing8);
Goods thing9 = new Goods("派件9", 8, 12);
goodsList.add(thing9);
Goods thing10 = new Goods("派件10", 2, 13);
goodsList.add(thing10);
Goods thing11 = new Goods("派件11", 12, 14);
goodsList.add(thing11);
Goods thing1 = new Goods("派件1", 1, 4);
goodsList.add(thing1);
Goods thing2 = new Goods("派件2", 3, 5);
goodsList.add(thing2);
Goods thing3 = new Goods("派件3", 0, 6);
goodsList.add(thing3);
Goods thing4 = new Goods("派件4", 5, 7);
goodsList.add(thing4);
Goods thing5 = new Goods("派件5", 3, 8);
goodsList.add(thing5);
Goods thing6 = new Goods("派件6", 5, 9);
goodsList.add(thing6);
Goods thing7 = new Goods("派件7", 6, 10);
goodsList.add(thing7);
return goodsList;
}
/**
* 打印货物
* @param goodsList
*/
public static void printGoods(List<Goods> goodsList)
{
for (Goods goods : goodsList)
{
System.out.print(goods.getName() + ":" + goods.getStartTime()
+ "-" + goods.getEndTime()+" ");
}
}
}
|
收藏
淘帖
踩
