public static double maxValue(int[] weight, int[] value, int capacity){ double[][] ratio=new double[weight.length][2]; for(int i=0;i< weight.length;i++){ ratio[i][0]=i; ratio[i][1]=value[i]/(double)weight[i]; } Arrays.sort(ratio,Comparator.comparingDouble(o->o[1])); double val=0; for(int i= weight.length-1;i>=0;i--){ int idx=(int)ratio[i][0]; if(capacity>=weight[idx]){ val+=value[idx]; capacity-=weight[idx]; } else{ val+=capacity*ratio[i][1]; capacity=0; break; } } return val; } public static void main(String[] args){ int[] weight={10,20,30}; int[] value={60,100,120}; int capacity=50; System.out.println(maxValue(weight,value,capacity)); }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter