DATA STRUCTURE ME LAB PROGRAMS-->9. 0/1 KNAPSACK USING DYNAMIC PROGRAMMING

 

0/1 KNAPSACK USING DYNAMIC PROGRAMMING

 

Program Coding:

 

import java.util.*;

import java.io.*;

import java.lang.*;

public class Knapsack01{

            static int n=5, W;

            static obj st[];

            public static BufferedReader br =new BufferedReader(new InputStreamReader(System.in));

            static class obj{

                        int weight;

                        int profit;

            }

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

                        int i=0;

                        System.out.println("Knap Sack Problem\n------------------\n");

                        System.out.print("Enter total number of objects: ");

                        n = Integer.parseInt( br.readLine() );

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

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

                        st = new obj[n+1];

                       

                        st[0] = new obj();

                        st[0].weight = st[0].profit = 0;

                       

                        for(i=1; i<=n; i++)

                       

{

            st[i] = new obj();

            System.out.print("For Object "+(i)+" :-\n\tWeight: ");

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

            System.out.print("\tProfit: ");

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

                        }

            System.out.print("\nOptimal Solution is : ");

            simple_fill();

            }

            static void simple_fill() {

                        int [][]s = new int[n+1][W+1];

                        for (int w = 0; w<= W; w++)  s[0][w] = 0;

                        for(int i=0; i<=n; i++) s[i][0]=0;

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

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

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

                                    {

                                                if (st[i].profit + s[i-1][w-st[i].weight] > s[i-1][w])

                                                            s[i][w] = st[i].profit + s[i-1][w- st[i].weight];

                                                else

                                                            s[i][w] = s[i-1][w];

                                    }

                                    else

                                                s[i][w] = s[i-1][w];

                        int i = n;

                        int k = W;

                        int prof = 0;

System.out.println("\n\nITEM\t\tWEIGHT\t\tPROFIT\n");             

while((i>0)&&(k>0))

                       

{

            if (s[i][k] != s[i-1][k])

            {

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

            k = k - st[i].weight;

            prof += st[i].profit;

            }

                        i--;

            }

                        System.out.print(" \nIt will yield a profit of Rs."+ prof);

            }

}

 

Output:

0/1 KNAPSACK USING DYNAMIC PROGRAMMING

 

Enter total no of objects3

Enter the max weight sack can take:10

For object 1:-

        Weight:4

          Profit:5

For object 2:-

        Weight:3

          Profit:7

For object 3:-

        Weight:2

           Profit:4

 

optimal solution:

 

 ITEM            WEIGHT          PROFIT

 

   3                     2                     Rs.4

   2                     3                     Rs.7

   1                     4                     Rs.5

 

It will yield a profit of Rs.16