public class fractionKnapsack { public static void main(String[] args) { int we [] = {15,40,30,35,30}; int val [] = {80,80,20,45,30}; int cap =75; double ratio[][] = new double[val.length][2]; for(int i=0;i<we.length;i++){ ratio[i][0] =i; ratio[i][1] = val[i]/(double)we[i]; } Arrays.sort(ratio, Comparator.comparingDouble(o -> o[1])); int pro=0; for(int i= ratio.length-1;i>=0;i--){ int ind = (int) ratio[i][0]; if(cap >=we[ind]){ cap-=we[ind]; pro+=val[ind]; }else{ pro+= ratio[i][1]*cap; cap=0; break; } } System.out.println(pro); }
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