Fractional Knapsack

Algorithm- Fractional Knapsack

import java.util.Scanner;

public class Knapsack01 {

     public static void main(String[] args) {

           Scanner scan = new Scanner(System.in);

           int n = scan.nextInt(); // 1

           int W = scan.nextInt(); // 1000

           float value[] = new float[n]; // 500

           float weight[] = new float[n]; // 30

           float ratio[] = new float[n];

           for (int i = 0; i < n; i++) {

                value[i] = scan.nextInt();

                weight[i] = scan.nextInt();

                ratio[i] = value[i] / weight[i];

           }

           float totalValue = knapSack01(W, value, weight, ratio, n);

           System.out.println(totalValue);

     }

     public static float knapSack01(float W, float[] value, float weight[], float ratio[],

                int n) {

           float V = 0;

           while (n>0 && W!=0) {

                int mI = maxIndex(n, ratio);

                float w=min(weight[mI],W);

                // W=40,weight[2]=30 // W=10,weight[0]=20;

                W = W - w;

                V = V + w*ratio[mI];

                weight[mI]=weight[mI]-w;

                ratio[mI] = 0;

                n--;

           }

           return V;

     }

     public static float min(float a,float b){

           return a>b?b:a;

     }

     public static int maxIndex(int n, float ratio[]) {

           float largest = Integer.MIN_VALUE;

           int lastIndex = 0;

           for (int i = 0; i < n; i++) {

                if (ratio[i] > largest) {

                     largest = ratio[i];

                     lastIndex = i;

                }

           }

           return lastIndex;

     }

}

Output:

Input: 3 50

60 20 100

50 120 30

Output: 180.0000

Simple Algorithms- Fibonacci,finding GCD & finding LCM

Algorithm 1- Finding Fibonacci number with better time complexity

import java.util.Scanner;

//0,1,1,2,3,5,8,13,21,34...

//fun(n)=fun(n-1)+fun(n-2) where n>=2

/*fib(9)=fib(8)+fib(7)

=fib(7)+fib(6)+fib(6)+fib(5)

=fib(6)+fib(5)+fib(5)+fib(4)+fib(5)+fib(4)+fib(4)+fib(3)

*/

public class FibonacciNumberFast {

     public static void main(String[] args) {

           Scanner scanner = new Scanner(System.in);

           int n = scanner.nextInt();

           long fno=fibonacciNumber(n);

           System.out.println(fno);  

     }

     public  static long fibonacciNumber(int n){

           int array[]= new int[n+1];

           array[0]=0;

           if(n==0)

                return array[0];

           array[1]=1;

           for(int i=2;i<=n;i++)

                array[i]=array[i-1]+array[i-2];

           return array[n];

     }

}

Algorithm 2– Finding GCD of a number

 1) GCD using Recursion

                          2) GCD using naïve approach

import java.util.Scanner;

// Largest number which divides both a and b

public class GCDNaive {

     public static void main(String[] args) {

           Scanner scanner = new Scanner(System.in);

           long a = scanner.nextLong();

           long b = scanner.nextLong();

           //long gcd = gcd(a, b);

           //System.out.println("Result from GCD Naive "+gcd);

           gcdFast(a, b);

     }

     static void gcdFast(long a, long b) {

           if (b == 0) {

                System.out.println(a);

           System.exit(0);

           }

           long rem=a%b;

           gcdFast(b, rem);

     }

/*   static long gcd(long a, long b) {

           long best = 0;

           for (long i = 1; i <= a + b; i++) {

                if ((a%i ==0) && (b%i== 0))

                     best = i;

           }

           return best;

     }

*/}

Algorithm 3– Finding LCM of a number

import java.util.Scanner;

// GCD(a,b)*LCM(a,b)=a*b

public class LCM {

     public static void main(String[] args) {

           Scanner scanner = new Scanner(System.in);

           long a = scanner.nextLong(); // 8

           long b = scanner.nextLong(); // 6

           // long c = gcd(a, b);

           // System.out.println("GCD is" + c);

           long c = gcdFast(a, b);

           long d = (a * b) / c;

           System.out.println(d);

     }

     static long gcdFast(long a, long b) {

           if (b == 0) {

                return a;

           }

           long rem = a % b;

           long c=gcdFast(b, rem);

           return c;

     }

     /*   static long gcd(long a, long b) {

           long best = 0;

           for (long i = 1; i <= a + b; i++) {

                if ((a % i == 0) && (b % i == 0))

                     best = i;

           }

           return best;

     }*/

}