Knapsack problem using Greedy-method in Java
By Sanskar DwivediIn this tutorial, we will learn some basics concepts of the Knapsack problem including its practical explanation.
We will also have a real-world implementation using Java program.
The knapsack problem is an optimization problem or a maximization problem.
It is also known as the Container loading problem.
Objective of Knapsack problem:
We have some objects and every object is having some weights, We are provided with a bag that bag is known as Knapsack
We have to fill the maximum objects in the bag according to their weights and profit so that the profit we get is maximum.
Constraints:
We will be provided by the object identification including their profits and weight.
The total weight of the objects filled in the bags should be less than the provided counter(m) which is given.
Example
Step 1:- Find profit/weight for each object.
Step 2:- Since we have to select whether we have to completely select the object or partially select it.
So we sort the profit/weight in descending order.
Step 3:-The object with the highest profit/weight is selected first.
Step 4:-Mark the object with 1 if it’s completely selected or the fraction part if it is not selected completely.
Step 5:-While we select a particular object, Deduct the knapsack size by its particular object size.
Step 6:-Repeat steps 4 & 5.
Step 7:-Note the final fraction part and count that object in the Knapsack(Remaining weight/Total weight).
Step 8:-Find the total weight (Summesion of weights*(Selected objects weight)).
We can take fractions; it is for those objects which are divisible.
Let some weight is 5 kg and we want only 2 kg so we select it.
Knapsack program in Java
import java.util.Scanner;
class Knapsack
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int object,m;
System.out.println("Enter the Total Objects");
object=sc.nextInt();
int weight[]=new int[object];
int profit[]=new int[object];
for(int i=0;i<object;i++)
{
System.out.println("Enter the Profit");
profit[i]=sc.nextInt();
System.out.println("Enter the weight");
weight[i]=sc.nextInt();
}
System.out.println("Enter the Knapsack capacity");
m=sc.nextInt();
double p_w[]=new double[object];
for(int i=0;i<object;i++)
{
p_w[i]=(double)profit[i]/(double)weight[i];
}
System.out.println("");
System.out.println("-------------------");
System.out.println("-----Data-Set------");
System.out.print("-------------------");
System.out.println("");
System.out.print("Objects");
for(int i=1;i<=object;i++)
{
System.out.print(i+" ");
}
System.out.println();
System.out.print("Profit ");
for(int i=0;i<object;i++)
{
System.out.print(profit[i]+" ");
}
System.out.println();
System.out.print("Weight ");
for(int i=0;i<object;i++)
{
System.out.print(weight[i]+" ");
}
System.out.println();
System.out.print("P/W ");
for(int i=0;i<object;i++)
{
System.out.print(p_w[i]+" ");
}
for(int i=0;i<object-1;i++)
{
for(int j=i+1;j<object;j++)
{
if(p_w[i]<p_w[j])
{
double temp=p_w[j];
p_w[j]=p_w[i];
p_w[i]=temp;
int temp1=profit[j];
profit[j]=profit[i];
profit[i]=temp1;
int temp2=weight[j];
weight[j]=weight[i];
weight[i]=temp2;
}
}
}
System.out.println("");
System.out.println("-------------------");
System.out.println("--After Arranging--");
System.out.print("-------------------");
System.out.println("");
System.out.print("Objects");
for(int i=1;i<=object;i++)
{
System.out.print(i+" ");
}
System.out.println();
System.out.print("Profit ");
for(int i=0;i<object;i++)
{
System.out.print(profit[i]+" ");
}
System.out.println();
System.out.print("Weight ");
for(int i=0;i<object;i++)
{
System.out.print(weight[i]+" ");
}
System.out.println();
System.out.print("P/W ");
for(int i=0;i<object;i++)
{
System.out.print(p_w[i]+" ");
}
int k=0;
double sum=0;
System.out.println();
while(m>0)
{
if(weight[k]<m)
{
sum+=1*profit[k];
m=m-weight[k];
}
else
{
double x4=m*profit[k];
double x5=weight[k];
double x6=x4/x5;
sum=sum+x6;
m=0;
}
k++;
}
System.out.println("Final Profit is="+sum);
}
}Output:
Enter the Total Objects 7 Enter the Profit 10 Enter the weight 2 Enter the Profit 5 Enter the weight 3 Enter the Profit 15 Enter the weight 5 Enter the Profit 7 Enter the weight 7 Enter the Profit 6 Enter the weight 1 Enter the Profit 18 Enter the weight 4 Enter the Profit 3 Enter the weight 1 Enter the Knapsack capacity 15 ------------------- -----Data-Set------ ------------------- Objects1 2 3 4 5 6 7 Profit 10 5 15 7 6 18 3 Weight 2 3 5 7 1 4 1 P/W 5.0 1.6666666666666667 3.0 1.0 6.0 4.5 3.0 ------------------- --After Arranging-- ------------------- Objects1 2 3 4 5 6 7 Profit 6 10 18 15 3 5 7 Weight 1 2 4 5 1 3 7 P/W 6.0 5.0 4.5 3.0 3.0 1.6666666666666667 1.0 Final Profit is=55.333333333333336
Hope this tutorial helped you.
Also read:
HI IAM KOKSK FROM INDIA.THANKS FOR THE PROGRAM SLIDE.ITS VERY USEFUL
thanks for code it’s so helpful….. 🙂