Java 算法（一）贪心算法
数据结构与算法目录(https://www.cnblogs.com/binarylei/p/10115867.html)
一、贪心算法
什么是贪心算法？是指在对问题进行求解时，总是做出当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所得出的结果仅仅是某种意义上的局部最优解。 因此贪心算法不会对所有问题都能得到整体最优解，但对于很多问题能产生整体最优解或整体最优解的近似解。
贪心算法的构成部分：
- 候选对象集合 ：候选添加进解的对象的结合·
解对象集合 ：初始时为空，逐步从候选对象集合添加
解判定函数 ：判定解是否己经完成(或候选对象集合是否还有可以添加的对象)
选择函数 ：从候选对象集合中按照贪心策略选择可用对象添加到解对象集合中
目标函数 ：记录解的值
二、0-1 背包问题
给定 n 种物品和一个背包。物品 i 的重量是 Wi，其价值为 Vi，背包的容量为 C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
经典的背包问题，这次选用贪心算法来解决，每次选择能装的物品中:
- 价值最大的
重量最小的
单位重量价值最大的
/**
* 贪心算法：0-1 背包问题
*/
public class GreedyAlgorithm {
// 候选对象
private Bag[] candidates;
// 背包的总承重
private int maxWeight;
// 解对象集合
private Set<Bag> resultSet = new HashSet<>();
// 解对象集合的值
private int result;
public GreedyAlgorithm(Bag[] candidates, int maxWeight) {
this.candidates = candidates;
this.maxWeight = maxWeight;
// 对背包按单位重量价值从大到小排序
Arrays.sort(candidates, Collections.reverseOrder());
}
public void select() {
int remainingWeight = maxWeight;
for (int i = 0; i < candidates.length; i++) {
Bag candidate = candidates[i];
// 判断当前物品是否可以放入背包中
if (check(candidate, remainingWeight)) {
result += candidate.value;
resultSet.add(candidate);
remainingWeight -= candidate.weight;
} else {
break;
}
}
}
// 判定解是否己经完成
public boolean check(Bag candidate, int remainingWeight) {
if (remainingWeight >= candidate.weight) {
return true;
}
return false;
}
public Set<Bag> getResultSet() {
return resultSet;
}
public int getResult() {
return result;
}
public static class Bag implements Comparable<Bag> {
// 物品重量
private int weight;
// 物品价值
private int value;
// 单位重量价值
private int unitValue;
public Bag(int weight, int value) {
this.weight = weight;
this.value = value;
this.unitValue = (weight == 0) ? 0 : value / weight;
}
@Override
public int compareTo(Bag bag) {
int value = bag.unitValue;
if (unitValue > value)
return 1;
if (unitValue < value)
return -1;
return 0;
}
}
}
每天用心记录一点点。内容也许不重要，但习惯很重要！
