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:
What is Thread-Safety and How to Achieve it?
Java Program to Implement Park-Miller Random Number Generation Algorithm
Spring Boot - Batch Service
Java Streams vs Vavr Streams
Toán tử trong java
The SpringJUnitConfig and SpringJUnitWebConfig Annotations in Spring 5
Java Program to Convert a Decimal Number to Binary Number using Stacks
Debug a JavaMail Program
Java Program to Check whether Directed Graph is Connected using BFS
Registration with Spring Security – Password Encoding
Check If Two Lists are Equal in Java
Spring JDBC
Generic Constructors in Java
New Features in Java 11
Java Program to Check if a Given Binary Tree is an AVL Tree or Not
Check if a String is a Palindrome in Java
Creating a Custom Starter with Spring Boot
Hướng dẫn Java Design Pattern – Memento
Java Program to Perform Search in a BST
A Guide to System.exit()
Ways to Iterate Over a List in Java
RegEx for matching Date Pattern in Java
Chương trình Java đầu tiên
Java 8 – Powerful Comparison with Lambdas
Java Program to Implement Hamiltonian Cycle Algorithm
A Guide to Iterator in Java
Calling Stored Procedures from Spring Data JPA Repositories
Java Program to Perform the Unique Factorization of a Given Number
Comparing Strings in Java
Java Program to Implement LinkedBlockingDeque API
Java Program to Find the Peak Element of an Array O(n) time (Naive Method)
Tính đa hình (Polymorphism) trong Java