1+ //Knapsack Algo
2+ import java .util .*;
3+
4+ class Element
5+ {
6+ double weight ,profit ,ratio ;
7+ int id ;
8+
9+ Element (double p ,double w )
10+ {
11+ profit =p ;
12+ weight =w ;
13+ ratio =p /w ;
14+ }
15+ }
16+
17+ class KnapSack
18+ {
19+ Scanner ip = new Scanner (System .in );
20+ int n ;
21+ double capacity ,currentCapacity ,profit =0 ;
22+ Element E [];
23+
24+ KnapSack (int x ,double y )
25+ {
26+ n =x ;
27+ capacity =y ;
28+ currentCapacity =capacity ;
29+ E =new Element [n ];
30+ inputData ();
31+ sortInc ();
32+ insert ();
33+ }
34+
35+ void inputData ()
36+ {
37+ for (int i =0 ;i <n ;i ++)
38+ {
39+ System .out .print ("Enter profit and weight of element " +(i +1 )+" : " );
40+ E [i ]=new Element (ip .nextDouble (),ip .nextDouble ());
41+ E [i ].id =i +1 ;
42+ }
43+ }
44+
45+ void sortInc () //Sort in increasing order of p/w ratio
46+ {
47+ for (int i =0 ;i <n ;i ++)
48+ {
49+ for (int j =i +1 ;j <n ;j ++)
50+ {
51+ if (E [i ].ratio <E [j ].ratio )
52+ {
53+ Element temp =E [i ];
54+ E [i ]=E [j ];
55+ E [j ]=temp ;
56+ }
57+ }
58+ }
59+ }
60+
61+ void insert ()
62+ {
63+ for (int i =0 ;currentCapacity !=0 ;i ++)
64+ {
65+ if (currentCapacity >=E [i ].weight )
66+ {
67+ System .out .println ("Insert Element " +E [i ].id );
68+ profit =profit +E [i ].profit ;
69+ currentCapacity =currentCapacity -E [i ].weight ;
70+ }
71+ else
72+ {
73+ double temp =currentCapacity /E [i ].weight ;
74+ profit =profit +temp *E [i ].profit ;
75+ System .out .println ("Insert Fraction " +temp +" of Element " +E [i ].id );
76+ currentCapacity =0 ;
77+ }
78+ }
79+ System .out .println ("Profit : " +profit );
80+ }
81+
82+
83+ }
84+
85+ class sjs7007_Knapsack
86+ {
87+ public static void main (String [] args )
88+ {
89+ Scanner ip = new Scanner (System .in );
90+ System .out .print ("Enter number of elements and capacity of Knapsack : " );
91+ int n =ip .nextInt (); //no. of elements
92+ double w =ip .nextDouble ();
93+ KnapSack K = new KnapSack (n ,w );
94+ }
95+ }
96+
97+ /* Output
98+
99+ Enter number of elements and capacity of Knapsack : 3 40
100+ Enter profit and weight of element 1 : 20 10
101+ Enter profit and weight of element 2 : 10 20
102+ Enter profit and weight of element 3 : 15 34
103+ Insert Element 1
104+ Insert Element 2
105+ Insert Fraction 0.29411764705882354 of Element 3
106+ Profit : 34.411764705882355
107+
108+ */
0 commit comments