## 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