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.
//This is a sample program to implement a fractional knapsack problem import java.io.IOException; import java.util.Scanner; class Fractional_Knapsack { public static void main(String args[]) throws IOException { int i,j=0,max_qty,m,n; float sum=0,max; Scanner sc = new Scanner(System.in); int array[][]=new int[2][20]; System.out.println("Enter no of items"); n=sc.nextInt(); System.out.println("Enter the weights of each items"); for(i=0;i<n;i++) array[0][i]=sc.nextInt(); System.out.println("Enter the values of each items"); for(i=0;i<n;i++) array[1][i]=sc.nextInt(); System.out.println("Enter maximum volume of knapsack :"); max_qty=sc.nextInt(); m=max_qty; while(m>=0) { max=0; for(i=0;i<n;i++) { if(((float)array[1][i])/((float)array[0][i])>max) { max=((float)array[1][i])/((float)array[0][i]); j=i; } } if(array[0][j]>m) { System.out.println("Quantity of item number: " + (j+1) + " added is " +m); sum+=m*max; m=-1; } else { System.out.println("Quantity of item number: " + (j+1) + " added is " + array[0][j]); m-=array[0][j]; sum+=(float)array[1][j]; array[1][j]=0; } } System.out.println("The total profit is " + sum); sc.close(); } }
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
Related posts:
Java Program to Find Basis and Dimension of a Matrix
How to Break from Java Stream forEach
How to Add a Single Element to a Stream
Java Program to Implement Self organizing List
Default Password Encoder in Spring Security 5
Validations for Enum Types
Java Program to Implement Max-Flow Min-Cut Theorem
Custom Exception trong Java
Getting Started with GraphQL and Spring Boot
Java Program to Implement TreeSet API
Simultaneous Spring WebClient Calls
Using a Custom Spring MVC’s Handler Interceptor to Manage Sessions
Java Program to Implement LinkedHashMap API
Java Program to Find Location of a Point Placed in Three Dimensions Using K-D Trees
Java Program to Implement Rolling Hash
ETL with Spring Cloud Data Flow
Spring Security Authentication Provider
Java Program to Check Whether a Directed Graph Contains a Eulerian Cycle
Serverless Functions with Spring Cloud Function
Easy Ways to Write a Java InputStream to an OutputStream
HttpClient 4 – Send Custom Cookie
Java Program to Implement Insertion Sort
Java String Conversions
“Stream has already been operated upon or closed” Exception in Java
Spring WebClient and OAuth2 Support
Java Program to Check whether Undirected Graph is Connected using BFS
A Guide to Java HashMap
Spring WebClient vs. RestTemplate
Extract links from an HTML page
Java Program to Create the Prufer Code for a Tree
A Guide to Apache Commons Collections CollectionUtils
Java Program to Implement AttributeList API