贪心法是从问题的某一个初始解出发，向给定的目标递推。推进的每一步要做一个当时看似最佳的贪心选择，不断地将问题实例归纳为更小的相似的子问题，并期望通过所做的局部最优选择产生出一个全局最优解。
问题是，这种局部贪心的选择是否可以得出全局最优解呢？在某些情况下是可以的。
例如：
【例 1】 键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。输出应包括所有去掉的数字的位置和组成的新的正整数。（N不超过240位）输入数据均不需判错。
算法分析：
首先我们必须注意，试题中正整数N的有效位数为240位，而计算机中整数有效位（包括符号位）充其量也不过11位，无论如何也达不到试题的数位要求。因此，必须采用可含256个字符的字串来代替整数。
以字串形式输入N，使用尽可能逼近目标的贪心法来逐一删去其中S个数符，每一步总是选择一个使剩下的数最小的数符删去。之所以作出这样贪心选择，是因为删S个数符的全局最优解，包含了删一个数符的子问题的最优解。
为了保证删1个数符后的数最小，我们按高位—>低位的方向搜索递减区间。若不存在递减区间，则删尾数符；否则删递减区间的首字符，这样形成了一个新数串。然后回到串首，重复上述规则，删下一数符……依次类推，直至删除S个数符为止。
例如：N = '178543'，S = 4，删数过程如下：
贪心法-删除实数
显然，按上述规则删去S个数符后，剩余N-S个数符组成的新数必定最小。
Java代码实现：
public class DeleteReal {
public static void main(String[] args) {
deleteReal(178543,4);
}
/**
* 删除实数处理方法
* @param real 实数
* @param s 删除次数
*/
private static void deleteReal(int real, int s){
System.out.println("删除前实数为：" + real + ", 删除次数为：" + s);
String realString = String.valueOf(real);
if (realString.length() < s) {
System.out.println("错误，实数的位数不能小于删除次数");
return;
}
String[] split = realString.split("");
ArrayList<String> list = new ArrayList<>(Arrays.asList(split));
while (s > 0) {
int index = 0;
for (; index < list.size() - 1; index ++){
if (Integer.valueOf(list.get(index))> Integer.valueOf(list.get(index + 1))) {
break;
}
}
list.remove(index);
s--;
}
StringBuilder sb = new StringBuilder();
list.stream().forEach(str -> sb.append(str));
String result = sb.toString();
System.out.println("贪心算法删除后的实数为：" + result);
}
}
执行结果：
删除前实数为：178543, 删除次数为：4
贪心算法删除后的实数为：13
对于一个最优化问题，我们怎样才能知道它是否适用于贪心算法求解？没有一个通用的方法。但适用于贪心策略求解的大多数问题都有两个特点：
- 贪心选择性质——可通过做局部最优（贪心）选择来达到全局最优解
贪心政策通常是自顶向下做的。第一步为一个贪心选择，将原问题变成一个相似的、但规模更小的问题，而后的每一步都是当前看似最佳的选择。这种选择可能依赖于已作出的所有选择，但不依赖有待于做的选择或子问题的解。从求解的全过程来看，每一次贪心选择都将当前问题归纳为更小的相似子问题，而每一个选择都仅做一次，无重复回溯过程。因此贪心法有较高的时间效率。
- 最优子结构——问题的最优解包含了子问题的最优解
对所有具备最优子结构的问题是否都可采用贪心策略呢？不一定，下面我们来考察一个经典优化问题的两种变形。
【例 2】背包问题
有一个贼在偷窃一家商店时发现有N件物品：第 i 件物品值 Vi 元，重 Wi ，(1 <= i <= n)，此处 Vi 和 Wi 都是整数。他希望带走的东西越值钱越好，但他的背包中最多只能装下 W 磅的东西（ W 为整数）。有两种偷窃方式：
- 0-1 背包问题
如果每件物品或被带走或被留下，小偷应该带走哪几件东西？ - 部分背包问题
如果允许小偷可带走某个物品的一部分，小偷应该带走哪几件东西，每件东西的重量是多少？
算法分析：
两种背包问题都具有最优化结构性质：
对于 0-1 背包问题，考虑重量至多为W磅的最值钱的一包东西。如果我们从中去掉物品 j ，余下的必须是窃贼从其余的 n - 1 件物品中可带走的重量至多为 W - Wj 的最值钱的一件东西；如果我们再从中去掉物品 i ，余下的也必须是窃贼从其余 n - 2 件可带走的、重量至多为 W - Wj - Wi 的最值钱的一件东西······，依次类推。
对于部分背包问题，如果我们考虑从最优货物中去掉某物品 J 的重量 Wp (Wj >= Wp)，则余下的物品必须是窃贼可以从 N - 1件原有物品和物品 J 的 Wj - Wp 中可带走的、重量至多为 W - Wp 的最值钱的一件东西······，依次类推。
我们可采用贪心策略来解决部分背包问题：
先对每件物品计算其每磅价值 Vi / Wi ，然后按每磅价值单调递减的顺序对所有物品排序。例如，总共有三件物品和一个背包。
背包问题
Java代码实现：
public class BackpackIssue {
public static void main(String[] args) {
new BackpackIssue().action();
}
private class Item {
private String name;
private int weight;
private int price;
Item(String name, int weight, int price){
this.name = name;
this.weight = weight;
this.price = price;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getPrice() {
return price;
}
public void setPrice(int price) {
this.price = price;
}
@Override
public String toString(){
return name + "的重量是：" + weight + "磅，价格是：" + price + "。";
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
private class Backpack extends Item {
private List<Item> items;
private int lastWeight;
Backpack(String name, int weight) {
super(name, weight, 0);
lastWeight = weight;
this.items = new ArrayList<>();
}
public void addItem (Item item) {
this.items.add(item);
subWeight(item.getWeight());
addPrice(item.getPrice());
}
public int getLastWeight() {
return lastWeight;
}
public void subWeight(int weight) {
this.lastWeight -= weight;
}
public void addPrice(int price) {
this.setPrice(this.getPrice() + price);
}
public void print(){
this.items.stream().forEach(System.out::println);
}
}
private void action(){
Item good1 = new Item("物品1", 10,60);
Item good2 = new Item("物品2", 20,100);
Item good3 = new Item("物品3", 30,120);
Backpack backpack = new Backpack("背包", 50);
count(new ArrayList<>(Arrays.asList(good1, good2, good3)), backpack);
}
private void count(List<Item> goods, Backpack backpack){
sort(goods);
goods.stream().forEach(g -> {
if (g.getWeight() <= backpack.getLastWeight()){
backpack.addItem(g);
}
else if (backpack.getLastWeight() > 0) {
int v = g.getPrice() / g.getWeight();
Item itemG = new Item(g.name + "_部分" ,backpack.getLastWeight(), v * backpack.getLastWeight());
backpack.addItem(itemG);
}
});
backpack.print();
}
private void sort(List<Item> goods){
goods.stream().sorted((n1,n2) -> {
int v1 = n1.price / n1.weight;
int v2 = n2.price / n2.weight;
if (v1 >= v2) {
return 1;
}
else{
return -1;
}
});
}
}
执行结果：
物品1的重量是：10磅，价格是：60。
物品2的重量是：20磅，价格是：100。
物品3_部分的重量是：20磅，价格是：80。
由此可见，在部分背包问题中，当我们在考虑是否把一件物品加到背包中时，不需要把加入该物品的子问题解与不取该物品的子问题解加以比较。由这种贪心方式所形成的所有子问题是互相独立的。
若对0-1背包问题采取贪心策略的话，顺序取物品1和2。
但是从下图可以看出，最优解取的是物品2和3，没有取物品1。两种包含物品1的可能解都不是最优解。
背包0-1
在0-1背包问题中不应该取物品1的原因在于这样无法将背包填满，空余的空间降低了它的每磅价值，因此当我们考虑是否要把一件物品加到背包中时，必须对把加进该物品的子问题的解与不取该物品的子问题的解进行比较。由这种方式的形成的子问题导致了许多重迭的子问题。对于这一类虽具有最优化结构性质、但产生的子问题互为重迭的试题，一般采用动态程序设计的方法求解。
网友评论