knapsack


See On Github

Data

Contributor

Generic placeholder thumbnail

by sjs7007

in java

Source Code

//Knapsack Algo
import java.util.*;

class Element
{
	double weight,profit,ratio;
	int id;

	Element(double p,double w)
	{
		profit=p;
		weight=w;
		ratio=p/w;
	}
}

class KnapSack
{
	Scanner ip = new Scanner(System.in);
	int n;
	double capacity,currentCapacity,profit=0;
	Element E[]; 

	KnapSack(int x,double y)
	{
		n=x;
		capacity=y;
		currentCapacity=capacity;
		E=new Element[n]; 
		inputData();
		sortInc();
		insert();
	}

	void inputData()
	{
		for(int i=0;i<n;i++)
		{
			System.out.print("Enter profit and weight of element " +(i+1)+" : ");
			E[i]=new Element(ip.nextDouble(),ip.nextDouble()); 
			E[i].id=i+1;
		}
	}

	void sortInc() //Sort in increasing order of p/w ratio
	{
		for(int i=0;i<n;i++)
		{
			for(int j=i+1;j<n;j++)
			{
				if(E[i].ratio<E[j].ratio)
				{
					Element temp=E[i];
					E[i]=E[j];
					E[j]=temp;
				}
			}
		}
	}

	void insert()
	{
		for(int i=0;currentCapacity!=0;i++)
		{
			if(currentCapacity>=E[i].weight)
			{
				System.out.println("Insert Element "+E[i].id);
				profit=profit+E[i].profit;
				currentCapacity=currentCapacity-E[i].weight;
			}
			else
			{
				double temp=currentCapacity/E[i].weight;
				profit=profit+temp*E[i].profit;
				System.out.println("Insert Fraction "+temp+" of Element "+E[i].id);
				currentCapacity=0;
			}
		}
		System.out.println("Profit : "+profit);
	}


}

class sjs7007_Knapsack
{
	public static void main(String[] args) 
	{
		Scanner ip = new Scanner(System.in);
		System.out.print("Enter number of elements and capacity of Knapsack : ");
		int n=ip.nextInt(); //no. of elements
		double w=ip.nextDouble();	
		KnapSack K = new KnapSack(n,w);
	}
}

/* Output

Enter number of elements and capacity of Knapsack : 3 40
Enter profit and weight of element 1 : 20 10
Enter profit and weight of element 2 : 10 20
Enter profit and weight of element 3 : 15 34
Insert Element 1
Insert Element 2
Insert Fraction 0.29411764705882354 of Element 3
Profit : 34.411764705882355

*/