贪心算法之圣诞老人的礼物

<>问题描述

圣诞节来临了，中圣诞老人准备分发糖果，现在有多箱不同的糖果，每箱糖果有自己的价值和重量，每箱糖果都可以拆分成任意散装组合带走，圣诞老人的寻路雪橇最多只能装下重量W的糖果，请问圣诞老人最多能带走多大价值的糖果。
输入
第一行由两个部分组成，分别为糖果箱数正整数n(1<=n<=100),驯鹿能承受的最大重量
正整数w(0<w<10000),两个数用空格隔开，其余n行每行对应一箱糖果，由两部分组成，分别为一箱糖果的价值正整数v和重量正整数w,中间用空格隔开
输出
输出圣诞老人能带走的糖果的最大总价值，保留1位小数，输出为一行，以换行符结束。
样例输入

4 15
100 4
412 8
266 7
591 2

样例输出

1193.0

<>算法思路

要使得拿走的糖果价值最大，拿走的糖果重量是一定的，我们就要优先挑选价值大的糖果，即价值重量比大的那些糖果。
解法：
按礼物的价值/重量比从大到小依次选取礼物，对选取的礼物尽可能多的装，直到达到总重量w
复杂度：O(nlogn)
package mooc; import java.util.ArrayList; import java.util.Collections; import
java.util.List; import org.junit.Test; public class test圣诞老人的礼物 { public class
Candy implements Comparable<Candy>{ public int v; public int w; public Candy(int
v, int w) { super(); this.v = v; this.w = w; } @Override
//重写比较方法，按照价值重量比从大到小的方式进行排序 public int compareTo(Candy o) { if(this.v==o.v&&this
.w==o.w){ return 0; } double result=((double)this.v/this.w)-((double)o.v/o.w);
if(result>0){ return -1; }else{ return 1; } } @Override public String toString()
{ return "Candy [v=" + v + ", w=" + w + "]"; } } public double MaxSumValue(int n
,int weight,int v[],int w[]){ List<Candy> list=new ArrayList<>();
//将糖果的价值和重量添加到集合中去 for(int i=0;i<n;i++){ list.add(new Candy(v[i],w[i])); } //排序
Collections.sort(list); //保存结果 double result=0.0; int tmpweight=weight;
//保存每次选取糖果之后可容纳的剩余重量 for(int i=0;i<n;i++){ //当可容纳的容量够大时，就把这个糖果拿走，并更新价值和剩余重量 if(
list.get(i).w<tmpweight){ result+=list.get(i).v; tmpweight-=list.get(i).w; }else
{ //当可容纳的容量不够大，就要进行拆分 result+=((double)list.get(i).v/list.get(i).w)*(tmpweight);
break; } } return result; } @Test public void test(){ int n=4,weight=15; int v[]
={100,412,266,591}; int w[]={4,8,7,2}; double x=MaxSumValue(n,weight,v,w);
System.out.println(x); } }
这样的算法称之为贪心算法
证明
替换法。对于用非此法选取的最大价值糖果箱序列，可以将其按照价值/重量比从大到小排列后得到
序列1：a1,a2,…
用序列1和安上述揭发选取的序列2进行比较
序列2：b1,b2
价值/重量比相同的若干箱糖果，可以合并成一箱，所以两个序列中元素都不重复
对于发现的第一个ai!=bi，则必有ai<bi
则在序列1中，用bi这种糖果，替代若干重量ai的这种糖果，会使得序列1的总价值增加，这和序列1时价值最大的取法矛盾
所以：序列1=序列2（序列2不可能时序列1的一个前缀且比序列1短）

<>贪心算法

每一步行动总是按照某种指标选取最优的操作来进行，该指标只看眼前，并不考虑以后可能造成的影响。
贪心算法需要证明其正确性
圣诞老人礼物题，若糖果只能整箱拿，则贪心法错误。
考虑下面例子
3个箱子(8,6)(5,5)(5.5),雪橇总容量10

• « 上一篇：html的ajax请求
• » 下一篇： 人员表设计思想 —— 也许会有点帮助