0/1KNAPSACK USING DYNAMIC PROGRAMMING

PROGRAM:

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;

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

{

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

{

System.out.print(i+":("+st[i].weight+", 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:

C:\j2sdk1.4.2_02\bin>javac Knapsack01.java

C:\j2sdk1.4.2_02\bin>java Knapsack01

Knap Sack Problem

------------------

Enter total number of objects: 3

Enter the maximum weight sack can take: 12

For Object 1 :-

        Weight: 5

        Profit: 6

For Object 2 :-

        Weight: 3

        Profit: 4

For Object 3 :-

        Weight: 7

        Profit: 6

Optimal Solution is : { 3:(7, Rs.6),  1:(5, Rs.6),   }

It will yield a profit of Rs.12