©2020-2024 ioDraw All rights reserved
<> Problem description
Christmas is coming , Santa Claus is going to distribute candy , There are many different boxes of candy now , Each box of candy has its own value and weight , Each box of candy can be split into any bulk combination to take away , Santa's Pathfinder sleigh can only hold weight at most W Candy , How much candy can Santa Claus take away at most .
input
The first line consists of two parts , They are positive integers of the number of candy boxes respectively n(1<=n<=100), The maximum weight a reindeer can bear
positive integer w(0<w<10000), The two numbers are separated by spaces , rest n Each line corresponds to a box of candy , It consists of two parts , Is the positive integer of the value of a box of candy v And weight positive integer w, The middle is separated by a space
output
Output the maximum total value of candy that Santa can take away , retain 1 Decimal place , Output as one line , End with newline .
sample input
4 15
100 4
412 8
266 7
591 2
sample output
1193.0
<> Algorithm idea
Make the candy you take the most valuable , The weight of the candy is certain , We should give priority to the selection of candy with high value , That is, those candies with a higher value to weight ratio .
solution ：
According to the value of the gift / Choose gifts in order of weight ratio , Pack as many gifts as possible , Until the total weight is reached w
Complexity ：O(nlogn)
package mooc; import java.util.ArrayList; import java.util.Collections; import
java.util.List; import org.junit.Test; public class test Santa's gift { 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
// Rewrite comparison method , Sort according to the value to weight ratio from large to small 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<>();
// Add the value and weight of candy to the collection for(int i=0;i<n;i++){ list.add(new Candy(v[i],w[i])); } // sort
Collections.sort(list); // Save results double result=0.0; int tmpweight=weight;
// Save the remaining weight that can be accommodated after each candy selection for(int i=0;i<n;i++){ // When the capacity is large enough , Take this candy away , And update the value and remaining weight if(
list.get(i).w<tmpweight){ result+=list.get(i).v; tmpweight-=list.get(i).w; }else
{ // When the capacity is not large enough , It's about to be split 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); } }
Such an algorithm is called greedy algorithm
prove
Substitution method . For the maximum value candy box sequence not selected by this method , It can be valued / The weight ratio is obtained after arranging from large to small
sequence 1：a1,a2,…
Use sequence 1 The sequence selected by he'an for the above disclosure 2 Compare
sequence 2：b1,b2
value / Several boxes of candy with the same weight ratio , Can be combined into a box , So the elements in both sequences are not repeated
For the first one found ai!=bi, There must be ai<bi
Then in the sequence 1 in , use bi This candy , Replace several weights ai This kind of candy , Will make the sequence 1 Increase in total value of , This is the same as the sequence 1 The contradiction of taking the method with the greatest value
therefore ： sequence 1= sequence 2（ sequence 2 Impossible sequence 1 A prefix and ratio sequence of 1 short ）
<> Greedy Algorithm
Each action is always carried out by selecting the best operation according to some index , This indicator only looks at the present , It does not consider the possible impact in the future .
Greedy algorithm needs to prove its correctness
Santa Gift question , If candy can only be taken in a whole box , Then the greedy method is wrong .
Consider the following example
3 A box (8,6)(5,5)(5.5), Total sled capacity 10
Technology