import java.util.*; public class FractionalKnapSnack { private static double calculateMaxP(Item[] ar,int w,Map<Integer,Double> hm) { Arrays.sort(ar,( a, b)->{ double d1=(double)(a.profit/a.weight); double d2=(double)(b.profit/b.weight); if(d1<d2){ return 1; } return -1; }); double res=0; for(int i=0;i<ar.length;i++){ if(w-ar[i].weight>=0){ w=w-ar[i].weight; res+=ar[i].profit; hm.put(ar[i].no,1D); }else{ res+=((w*1.0d)/ar[i].weight)*ar[i].profit; hm.put(ar[i].no,(w*1.0d)/ar[i].weight) ; break; } } return res; } public static void main(String[] args) { Scanner sc=new Scanner(System.in); System.out.println("enter no of objects"); int n=sc.nextInt(); System.out.println("enter the total weight of the knapsnack"); int w=sc.nextInt(); Item [] ar=new Item[n]; for(int i=0;i<n;i++){ System.out.println("enter profit for item :"+(i+1)); int p=sc.nextInt(); System.out.println("enter weight for item :"+(i+1)); int wi=sc.nextInt(); Item it=new Item(p, wi,i+1); ar[i]=it; } Map<Integer,Double> sol=new LinkedHashMap<>(); double res=calculateMaxP(ar,w,sol); System.out.println(res); System.out.println(sol); } } public class Item{ int profit; int weight; int no; Item(int p,int w,int no){ profit=p; weight=w; this.no=no; } }
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