贪心策略

贪心策略

每一步都踩去当前状态下的最优的选择（局部最优解），从而希望推导出全局最优解。

1、有一天，海盗们截获了一搜船，每一件古董都价值连城。海盗船的载重为W，每件古董的重量为Weight ,海盗们该如何把尽可能多数量的古董装上海盗船。

比如W为30 Weight 分别为3、5、4、10、7、14、2、11

贪心策略：每一次都优先选择重量最小的古董

public class Main1 {
	
	
	public static void main(String[] args) {
		
		int weights[]= {3,5,4,10,7,14,2,11};
		//装上船的重量
		int weight=0;
		//装上船的古董数量
		int count=0;
		//古董的总价值
		int capacity=30;
		//先对古董重量进行排序
		Arrays.sort(weights);
		for(int i=0;i<weights.length&&weight<capacity;i++) {
			weight+=weights[i];
			if(weight<=30) {
				count++;
				System.out.println(weights[i]);
			}
		}
		System.out.println("一共选了"+count+"件古董");
		
	}

}

2、假设有25分、10分、5分、1分的硬币，现在要找给顾客41分的零钱，如何办到硬币个数最少

public class Main2 {
	public static void main(String[] args) {
		int coins[]= {25,10,5,1};
		int money=41;
		//硬币个数
		int count=0;
		Arrays.sort(coins);
		for(int i=coins.length-1;i>=0;i--) {
			if(money<coins[i]) continue;
			System.out.println("找了"+coins[i]+"分钱");
			money-=coins[i];
			count++;
			i=coins.length;
		}
		System.out.println("一共找了"+count+"枚硬币");
	}
}

上面一种做法，每次当做一次循环后，i要重新赋值为数组中最后一个元素的索引，这样看起来不太美观。所以提供下面一种思路

public class Main2{
public static void main(String []args){
Integer coins[]= {25,10,5,1};
		int money=41;
		//从数组第一位开始取值
		int i=0;
		//硬币个数
		int count=0;
		//降序排序
		Arrays.sort(coins,(Integer f1,Integer f2)->f2-f1);
		while(i<coins.length) {
			//需要找的钱比最大的硬币都要小，直接跳过
			if(money<coins[i]) {
				i++;
				continue;
			}
			money-=coins[i];
			count++;
		}
		System.out.println(count);
}
}

上述第一个问题中，古董的数量是不可以重复取的，而第二个问题中，硬币的数量是可以重复取的。这都是比较简单的贪心策略。

3、我们换一种硬币。比如我们现在有25分、20分、5分、1分，还是一样需要找41分的零钱。

如果我们按照刚才的思路，每一次都优先选择面值最大的硬币.

那么我们的解为:25->5->5->5->1 一共是五枚硬币.

public class Main3{

public static void main(String[] args){
  Integer coins[]= {25,20,5,1};
  int money=41;
  //从小到大排列
  Arrays.sort(coins);
  int count=0;
  int index=coins.length-1;
  while(index>0){
    while(money>=coins[index]){
      money-=coins[index];
      count++;
    }
    index--;
  }
System.out.println(count);
}
}

实际上本题的最优解为:20->20->1 一共是三枚硬币.

这说明我们的贪心策略出问题了吗，按照常识来说，每一次都选择最大的，这样得出的数量最少也没有什么问题。

所以贪心策略并不一定能得到全局最优解，我们只是希望每次都取到局部最优解，进而能得到全局最优解。

因为我们一般没有测试所有可能的解，容易过早做决定，所以没法达到全局最佳解。 换句话说：如果我们要测试所有可能的解，那就变成了暴力法。

贪心策略只注重局部的利益最大化，但是看不到长远的未来，走一步看一步。每一次都是选择当前最优解。

但是贪心算法简单、高效，一般不需要穷举所有的可能。所以我们一般拿来作为其他算法的辅助算法。

4、0-1背包问题

有n件物品和一个最大承重为W的背包，每件物品的重量为weight，价值为value

·在保证总重量不超过W的前提下，将哪几件物品装入背包，可以使得背包的总价值最大？

·每个物品只有一件，也就是说每个物品只能选择0件或者1件

如果我们采取贪心策略：一共有三种方案

1）价值主导，优先选择价值最高的物品放进背包

2）重量主导，优先选择重量最轻的物品放进背包

3）价值密度主导，优先选择价值密度最高的物品放进背包（价值密度=价值/重量）

假设背包最大承重为150

如果以价值为主导,我们将4,2,6,5号物品放进背包，总价值为165，总重量为130

如果我们以重量为主导，我们将6,7,2,1,5号物品放进背包，总价值为155，总重量为140

如果我们以价值密度为主导，我们将6，2，7，4，1号物品放进背包，总价值为170，总重量为150

不难看出，第三种解法是最好的。

我们可以先模仿一下以价值为主导的思路.

首先创建背包类

public class Pack {

	
	public  int weight;
	public int value;
	public double density;
	public Pack(int weight,int value) {
		this.weight=weight;
		this.value=value;
		density=value*1.0/weight;
		
	}
	@Override
	public String toString() {
		return "pack [weight=" + weight + ", value=" + value + ", density=" + density + "]";
	}
	
}

public class Main3 {
	
	public static void main(String[] args) {
		//以价值为主导,对物品价值进行降序排列
		select((Pack p1,Pack p2)->{
			return p2.value-p1.value;
		});
		
				
	}
	
	static void select(Comparator<Pack> cmp) {
		Pack[]pack=new Pack[] {
				new Pack(35,10),new Pack(30,40),new Pack(60,30),new Pack(50,50),
				new Pack(40,35),new Pack(10,40),new Pack(25,30)
				};
		Arrays.sort(pack,cmp);
		int capacity=150;
		//当前背包重量
		int totalWeight=0;
		//总价值
		int totalValue=0;
		List<Pack>list=new ArrayList<>();
		
		for(int i=0;i<pack.length&&totalWeight<capacity;i++) {
		     int newWeight=totalWeight+pack[i].weight;
		     if(newWeight<=capacity) {
		    	 totalWeight=newWeight;
		    	 totalValue+=pack[i].value;
		    	 list.add(pack[i]);
		     }
		}
		
		
		for(int i=0;i<list.size();i++) {
			System.out.println(pack[i]);
		}
		System.out.println("===================================");
       System.out.println("总价值是"+totalValue);	
      
		
	}

}

最后我们得出结果

同样的，如果我们需要以重量为主导或者以价值密度为主导。只需要改动一点点

public static void main(String[] args) {
		//以价值为主导,对物品价值进行降序排列
		select((Pack p1,Pack p2)->{
			return p2.value-p1.value;
		});
		//以重量为主导,对物品重量进行升序排列
		select((Pack p1,Pack p2)->{
			return p1.weight-p2.weight;
		});
		
		//价值密度主导,对物品价值密度降序排列
		select((Pack p1,Pack p2)->{
			return Double.compare(p2.density, p1.density);
			
		});
		
		
				
	}

最后得出的结果如下图所示

赏

谢谢你请我喝奶茶

微信