Java Program to Solve the Fractional Knapsack Problem

This is a java program to implement a standard fractional knapsack problem. It is an algorithmic problem in combinatorial optimization in which the goal is to fill a container (the “knapsack”) with fractional amounts of different materials chosen to maximize the value of the selected materials.

Here is the source code of the Java Program to Solve the Fractional Knapsack Problem. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a sample program to implement a fractional knapsack problem
  2. import java.io.IOException;
  3. import java.util.Scanner;
  4.  
  5. class Fractional_Knapsack  
  6. {  
  7.     public static void main(String args[]) throws IOException  
  8.     {  
  9.         int i,j=0,max_qty,m,n;  
  10.         float sum=0,max;  
  11.         Scanner sc = new Scanner(System.in);
  12.         int array[][]=new int[2][20];  
  13.         System.out.println("Enter no of items");  
  14.         n=sc.nextInt(); 
  15.  
  16.         System.out.println("Enter the weights of each items");
  17.         for(i=0;i<n;i++)  
  18.             array[0][i]=sc.nextInt();    
  19.  
  20.         System.out.println("Enter the values of each items");
  21.         for(i=0;i<n;i++)  
  22.             array[1][i]=sc.nextInt(); 
  23.  
  24.         System.out.println("Enter maximum volume of knapsack :");  
  25.         max_qty=sc.nextInt();  
  26.  
  27.         m=max_qty;  
  28.         while(m>=0)  
  29.         {  
  30.             max=0;  
  31.             for(i=0;i<n;i++)  
  32.             {  
  33.                 if(((float)array[1][i])/((float)array[0][i])>max)  
  34.                 {  
  35.                     max=((float)array[1][i])/((float)array[0][i]);  
  36.                     j=i;  
  37.                 }  
  38.             }  
  39.             if(array[0][j]>m)  
  40.             {  
  41.                 System.out.println("Quantity of item number: " +  (j+1) + " added is " +m);  
  42.                 sum+=m*max;  
  43.                 m=-1;  
  44.             }  
  45.             else  
  46.             {  
  47.                 System.out.println("Quantity of item number: " + (j+1) + " added is " + array[0][j]);  
  48.                 m-=array[0][j];  
  49.                 sum+=(float)array[1][j];  
  50.                 array[1][j]=0;  
  51.             }  
  52.         }  
  53.         System.out.println("The total profit is " + sum);
  54.         sc.close();
  55.     }  
  56. }

Output:

$ javac Fractional_Knapsack.java
$ java Fractional_Knapsack
 
Enter no of items
5
Enter the weights of each items
10 20 30 40 50
Enter the values of each items
5 4 3 2 1
Enter maximum volume of knapsack :
80
Quantity of item number: 1 added is 10
Quantity of item number: 2 added is 20
Quantity of item number: 3 added is 30
Quantity of item number: 4 added is 20
The total profit is 13.0

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.