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;
}
