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