Design and Analysis of Algorithm Lab 6 | Read Now

Design and Analysis of Algorithm Lab 6

6] Implement in Java, the 0/1 Knapsack problem using

• A] Dynamic Programming method
• B] Greedy method

6A] Program code

import java.util.Scanner;
public class lab6a 
{
    static int max(int a, int b) 
    { 
        return (a > b)? a : b; 
    }
    static int knapSack(int W, int wt[], int val[], int n)
    {
        int i, w;
        int [][]K = new int[n+1][W+1];
        for (i = 0; i <= n; i++)
        {
            for (w = 0; w <= W; w++)
            {
                if (i==0 || w==0)
                    K[i][w] = 0;
                else if (wt[i-1] <= w)
                    K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
                else
                    K[i][w] = K[i-1][w];
            }
        } 
        return K[n][W];
    }
 
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the number of items: ");
        int n = sc.nextInt();
        System.out.println("Enter the items weights: ");
        int []wt = new int[n];
        for(int i=0; i<n; i++)
            wt[i] = sc.nextInt();
 
        System.out.println("Enter the items values: ");
        int []val = new int[n];
        for(int i=0; i<n; i++)
            val[i] = sc.nextInt();
 
        System.out.println("Enter the maximum capacity: ");
        int W = sc.nextInt();
 
        System.out.println("The maximum value that can be put in a knapsack of capacity W is: " + knapSack(W, wt, val, n));
        sc.close();
    }
}

Output

6B] Program Code

import java.util.Scanner;
public class lab6b
{
	public static void main(String[] args) 
	{
	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