贪心算法
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
算法应用
海盗装宝问题
海盗找到宝藏后，发现背包不够大，怎样装宝贝，才能最值钱呢。
/**
* 海盗装宝
*
* @author Naah
*
*/
public class haidaofenbao {
public static void main(String[] args) {
// TODO Auto-generated method stub
// 宝贝的重量数组
int[] weights = new int[] { 35, 40, 60, 50, 40, 20, 25 };
// 宝贝的价值数组
int[] values = new int[] { 10, 200, 30, 50, 35, 80, 30 };
haidaofenbao greedy = new haidaofenbao();
// 背包最大重量为100
greedy.put(100, weights, values);
}
/**
* 装宝算法
*
* @param maxWeight
* 背包最大重量
* @param weights
* 所有宝贝的重量数组
* @param values
* 所有宝贝的价值数组
*/
private void put(int maxWeight, int[] weights, int[] values) {
// 创建所有宝贝的性价比数组
double[] wv = new double[weights.length];
// 创建所有宝贝的性价比下标数组
int[] index = new int[weights.length];
// 循环计算所有宝贝的性价比
for (int i = 0; i < wv.length; i++) {
wv[i] = values[i] / weights[i];
index[i] = i;
}
// 以降序排序所有宝贝的性价比，以及下标
// 优先降序排序性价比，其次优先降序排序重量
// 简单选择排序
for (int i = 0; i < wv.length; i++) {
for (int j = i; j < wv.length; j++) {
// 如果i下标性价比小于j下标性价比
if (wv[i] < wv[j]) {
// 交换性价比
double temp = wv[i];
wv[i] = wv[j];
wv[j] = temp;
// 交换下标
int ind = index[i];
index[i] = index[j];
index[j] = ind;
// 如果i下标性价比等于j下标性价比
} else if (wv[i] == wv[j]) {
// 如果i下标宝贝的重量小于j下标宝贝的重量
if (weights[index[i]] < weights[index[j]]) {
// 交换性价比
double temp = wv[i];
wv[i] = wv[j];
wv[j] = temp;
// 交换下标
int ind = index[i];
index[i] = index[j];
index[j] = ind;
}
}
}
}
// 创建标记装宝数组
boolean[] flag = new boolean[weights.length];
// 创建目前背包重量变量
int bagWeight = 0;
// 创建目前背包价值变量
int bagValue = 0;
// 循环性价比数组进行装宝
for (int i = 0; i < wv.length; i++) {
// 如果目前背包能把该宝贝装下
if (weights[index[i]] + bagWeight <= maxWeight) {
// 目前背包重量增加
bagWeight = bagWeight + weights[index[i]];
// 目前背包价值增加
bagValue = bagValue + values[index[i]];
// 标记该宝贝已装
flag[index[i]] = true;
}
}
// 输出装宝后背包的重量
System.out.println("weight:" + bagWeight);
// 输出装宝后背包的价值
System.out.println("value:" + bagValue);
// 循环输出标记数组，查看背包中装入哪些宝贝
for (int i = 0; i < flag.length; i++) {
System.out.print(flag[i] + " ");
}
}
}
