Sunday, April 18, 2010

0/1 Knapsack problem using Dynamic Algo

import java.io.*;
class KSdyn
{
   public static void main(String args[])throws IOException
 {
   BufferedReader o=new BufferedReader(new InputStreamReader(System.in));
   int n,i,j;
  
   System.out.println("Enter the no of item");
   n=Integer.parseInt(o.readLine());
  
   int p[]=new int[n+1];
  
   int w[]=new int[n+1];
  
   System.out.println("Enter the profit");
   for(i=1;i<=n;i++)
   {
       p[i]=Integer.parseInt(o.readLine());
   }
   System.out.println("Enter the weight");
   for(j=1;j<=n;j++)
   {
       w[j]=Integer.parseInt(o.readLine());
   }
   System.out.println("enter the capacity of knapsack");
   int m=Integer.parseInt(o.readLine());
   knapsack(n,m,w,p);
 }
 static void knapsack(int n,int m,int w[],int p[])
 {
     int s[][]=new int[n+1][m+1];
    for(int W=0;W<=m;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 j=0;j<=m;j++)
        if (w[i]<=j)
         {
           if(p[i]+s[i-1][j-w[i]]>s[i-1][j])
              s[i][j]=p[i]+s[i-1][j-w[i]];
              else
              s[i][j]=s[i-1][j];
         }
         else
           s[i][j]=s[i-1][j];
     for(int i=0;i<=n;i++)
     
      {
      for(int j=0;j<=m;j++)
      {
      System.out.print(s[i][j]+" ");
      }
      System.out.println();
      }
        knapsack_item(s,w,n,m);  
 }
 static void knapsack_item(int s[][],int w[],int n,int m)
 {   int ans[]=new int[n];
     int i=n;
    int k=m;
    while (i>0&&k>0)
    {
        if (s[i][k]!=s[i-1][k])
        {
          ans[i]=1;
          k=k-w[i];
          //System.out.println("Item"+i+"is selected");
        }
        i--;
    }
   
    for(i=0;i
       if (ans[i]==1)
       {
           System.out.println("Item"+i+"is selected");
       }
   
 }
}/*Output:
Enter the no of item
4
Enter the profit
3
4
5
6
Enter the weight
2
3
4
5
enter the capacity of knapsack
5
0 0 0 0 0 0
0 0 3 3 3 3
0 0 3 4 4 7
0 0 3 4 5 7
0 0 3 4 5 7
Item1is selected
Item2is selected
*/             

0 comments:

Post a Comment

 
ShareThis

Visitor

Website counter
Copyright 2009 Code's. Powered by Blogger
Blogger Templates created by Deluxe Templates
Wordpress by Wpthemescreator
Blogger Showcase