0/1 KNAPSACK USING DYNAMIC PROGRAMMING

AIM

To write a Java program for the implementation of 0/1 knapsack using dynamic programming.

ALGORITHM

Step 1:              Start the program and define the function.

Step 2:              Initialize the weight and profit.

Step 3:              Read the number of objects that are given.

Step 4:              For each objects, print the profit and weight

Step 5:              Initializing is set to false.

Step 6:              Display and print the item weight and profit

Step 7:              Display the total cost

Step 8:              End of the program.

PROGRAM

0/1 KNAPSACK USING DYNAMIC PROGRAMMING

import java.io.*;

class objects

{

   int weight;

   int profit;

}

public class knapsack

{

    static int N,W;

    static objects st[];

    public static void main(String args[])throws IOException

    {

        DataInputStream in=new DataInputStream(System.in);

        System.out.println("Enter the number of objects:");

        N=Integer.parseInt(in.readLine());

        System.out.println("Enter the maximum weight sack can take:");

        W=Integer.parseInt(in.readLine());

        st=new objects[N+1];

        st[0]=new objects();st[0].weight=st[0].profit=0;

        for(int i=1;i<=N;i++)

        {

                st[i]=new objects();

                System.out.println("\nFor object "+i);

                System.out.print("Enter profit: ");

                st[i].profit=Integer.parseInt(in.readLine());

                System.out.print("Enter Weight: ");

                st[i].weight=Integer.parseInt(in.readLine());

        }

        int [][] opt=new int[N+1][W+1];

        boolean [][] sol= new boolean[N+1][W+1];

        for(int n=1;n<=N;n++)

        for(int w=1;w<=W;w++)

        {

            int option1=opt[n-1][w];

            int option2=-1;

            if(st[n].weight<=w)

               option2=st[n].profit+opt[n-1][w-st[n].weight];

            opt[n][w]=Math.max(option1, option2);

            sol[n][w]=(option2 > option1);

          }

        boolean take[]=new boolean[N+1];

        int prof=0;

        for(int n=N,w=W;n>0;n--)

           if(sol[n][w])

           {

             take[n]=true;

             w=w-st[n].weight;

             prof+=st[n].profit;

           }

           else

             take[n]=false;

        System.out.println("\nThe optimal solution is:");

        System.out.println("Item \t weight \t profit");

        for(int n=1;n<=N;n++)

          if(take[n])

            System.out.println(n+" \t "+st[n].weight+" \t\t "+st[n].profit);

        System.out.println("\n Total profit:"+prof);

   }

}

OUTPUT:

------

Enter the number of objects:

3

Enter the maximum weight sack can take:

10

For object 1

Enter profit: 20

Enter Weight: 6

For object 2

Enter profit: 10

Enter Weight: 2

For object 3

Enter profit: 19

Enter Weight: 3

The optimal solution is:

Item     weight          profit

1        6               20

3        3               19

 Total profit:39

  

RESULT

Thus the program for 0/1 knapsack using Java has been implemented.