Implementing 0-1 Knapsack in Java

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

In 0-1 Knapsack, the restriction is that, one cannot select fraction of any item. He/She must select either whole item or try with alternate one.

import java.io.*;
class knapo
{
void knapsack(int w[],int p[],int n,int m)
{
int s[][]=new int[n+1][m+1];
for(int wt=0;wt<=m;wt++) s[0][wt]=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];
}

knapsack_items(s,n,m,w,p);
}

void knapsack_items(int s[][],int n,int m,int w[],int p[])
{ int ans[]=new int[n+1];
int i=n;
int k=m;
int profit=0;
while (i>0 && k>0)
{
if (s[i][k]!=s[i-1][k])
{
ans[i]=1;
profit+=p[i];
k=k-w[i];
}
i–;
}

System.out.println(“values for element”);
for(i=1;i<=n;i++) System.out.println("Element "+i+":"+ans[i]); System.out.println("profit = "+profit); } } class knapmain { public static void main(String args[])throws IOException { knapo ob =new knapo(); BufferedReader obj=new BufferedReader(new InputStreamReader(System.in)); System.out.println("how many objects"); int n=Integer.parseInt(obj.readLine()); System.out.println("enter the capacity of bag"); int m=Integer.parseInt(obj.readLine()); int p[],w[]; p=new int[n+1]; w=new int[m+1]; System.out.println("enter the profit and weight"); for(int i=1;i<=n;i++) { System.out.print("P"+i+":"); p[i]=Integer.parseInt(obj.readLine()); System.out.print("W"+i+":"); w[i]=Integer.parseInt(obj.readLine()); System.out.println(); } ob.knapsack(w,p,n,m); } } /* output how many objects 4 enter the capacity of bag 15 enter the profit and weight P1:5 W1:6 P2:8 W2:9 P3:5 W3:6 P4:4 W4:7 Values for elements Element 1:1 Element 2:1 Element 3:0 Element 4:0 profit = 13 Process Exit... */ [/java]

Leave a Reply

Your email address will not be published. Required fields are marked *