21CS42 | DESIGN & ANALYSIS OF ALGORITHM | SEARCH CREATORS
Subject Code:21CS42
Subject :Design and Analysis of Algorithm
Program-04
4. To solve Knapsack problem using Greedy method
Theory Concept : Greedy Method
• The greedy method is one of the strategies like Divide and conquer used to
solve the problems.
• This method is used for solving optimization problems.
• An optimization problem is a problem that demands either maximum or
minimum results. Let's understand through some terms.
• This technique is basically used to determine the feasible solution that may
or may not be optimal.
• The feasible solution is a subset that satisfies the given criteria. The optimal
solution is the solution which is the best and the most favorable solution in
the subset.
• In the case of feasible, if more than one solution satisfies the given criteria
then those solutions will be considered as the feasible, whereas the optimal
solution is the best solution among all the solutions.
Search Creators… Page 1
21CS42 | DESIGN & ANALYSIS OF ALGORITHM | SEARCH CREATORS
Knapsack Algorithm
The weights (Wi) and profit values (Pi) of the items to be added in the knapsack are
taken as an input for the fractional knapsack algorithm and the subset of the items added
in the knapsack without exceeding the limit and with maximum profit is achieved as the
output.
Algorithm
• Consider all the items with their weights and profits mentioned
respectively.
• Calculate Pi/Wi of all the items and sort the items in descending order
based on their Pi/Wi values.
• Without exceeding the limit, add the items into the knapsack.
• If the knapsack can still store some weight, but the weights of other items
exceed the limit, the fractional part of the next time can be added.
• Hence, giving it the name fractional knapsack problem.
Examples
• For the given set of items and the knapsack capacity of 10 kg, find the
subset of the items to be added in the knapsack such that the profit is
maximum.
Items 1 2 3 4 5
Weights (in kg) 3 3 2 5 1
Profits 10 15 10 12 8
Search Creators… Page 2
21CS42 | DESIGN & ANALYSIS OF ALGORITHM | SEARCH CREATORS
Solution
Step 1
Given, n = 5
Wi = {3, 3, 2, 5, 1}
Pi = {10, 15, 10, 12, 8}
Calculate Pi/Wi for all the items
Items 1 2 3 4 5
Weights (in kg) 3 3 2 5 1
Profits 10 15 10 20 8
Pi/Wi 3.3 5 5 4 8
Step 2
Arrange all the items in descending order based on Pi/Wi
Items 5 2 3 4 1
Weights (in kg) 1 3 2 5 3
Profits 8 15 10 20 10
Pi/Wi 8 5 5 4 3.3
Step 3
Without exceeding the knapsack capacity, insert the items in the knapsack with
maximum profit.
Knapsack = {5, 2, 3}
Search Creators… Page 3
21CS42 | DESIGN & ANALYSIS OF ALGORITHM | SEARCH CREATORS
However, the knapsack can still hold 4 kg weight, but the next item having 5 kg weight
will exceed the capacity. Therefore, only 4 kg weight of the 5 kg will be added in the
knapsack.
Items 5 2 3 4 1
Weights (in kg) 1 3 2 5 3
Profits 8 15 10 20 10
Knapsack 1 1 1 4/5 0
Hence, the knapsack holds the weights = [(1 * 1) + (1 * 3) + (1 * 2) + (4/5 * 5)] = 10, with
maximum profit of [(1 * 8) + (1 * 15) + (1 * 10) + (4/5 * 20)] = 37.
Search Creators… Page 4
21CS42 | DESIGN & ANALYSIS OF ALGORITHM | SEARCH CREATORS
PROGRAM
package DAA_Programs;
import java.util.Scanner;
public class Knapsack_Problem_Using_Greedy_Method {
public static void main(String[] args)
{
int i,j,n;
float temp,m;
float p[] = new float[15];
float w[] = new float[15];
float c[] = new float[15];
System.out.println("\nEnter Number of Objects:");
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
System.out.println("\nEnter Weights:");
for(i=0;i<n;i++)
w[i] = sc.nextFloat();
System.out.println("\nEnter Profits:");
for(i=0;i<n;i++)
p[i]=sc.nextFloat();
System.out.println("\nEnter KnapSack Size:");
m=sc.nextInt();
for(i=0;i<n;i++)
Search Creators… Page 5
21CS42 | DESIGN & ANALYSIS OF ALGORITHM | SEARCH CREATORS
c[i]=p[i]/w[i];
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if(c[j]<c[j+1])
{
temp=c[j];
c[j]=c[j+1];
c[j+1]=temp;
temp=w[j];
w[j]=w[j+1];
w[j+1]=temp;
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
}
}
System.out.println("\nThe Items are Arranged as...\n");
System.out.println("\n\nItems\tWeights\tProfits");
for(i=0;i<n;i++)
System.out.println("\nx["+i+"]\t"+w[i]+"\t"+p[i]);
knapsack(n,m,w,p);
}
Search Creators… Page 6
21CS42 | DESIGN & ANALYSIS OF ALGORITHM | SEARCH CREATORS
public static void knapsack(int n,float m,float w[],float p[])
{
float x[]=new float[15];
float U,profit=0,weight=0;
int i;
U=m;
for(i=0;i<n;i++)
x[i]=0;
for(i=0;i<n;i++) {
if(w[i]>U)
break;
x[i]=1;
U=U-w[i];
}
if(i<n)
x[i]=U/w[i];
System.out.println("\nThe Solution Vector is:");
for(i=0;i<n;i++)
System.out.println("\n"+i+"\t"+x[i]);
for(i=0;i<n;i++) {
w[i]=w[i]*x[i];
p[i]=p[i]*x[i];
}
for(i=0;i<n;i++) {
profit = profit+p[i];
Search Creators… Page 7
21CS42 | DESIGN & ANALYSIS OF ALGORITHM | SEARCH CREATORS
weight = weight+w[i];
}
System.out.println("\nMaximum Profit is:");
System.out.println("\n\t\t"+profit);
System.out.println("\nMaximum Weight is:");
System.out.println("\n\t\t"+weight);
}
}
Search Creators… Page 8
21CS42 | DESIGN & ANALYSIS OF ALGORITHM | SEARCH CREATORS
OUTPUT
Search Creators… Page 9
21CS42 | DESIGN & ANALYSIS OF ALGORITHM | SEARCH CREATORS
Search Creators… Page 10
