PART A
(PART A: TO BE REFFERED BY STUDENTS)
Experiment No.04
A.1 Aim:
Write a program to implement Knapsack Problem using Greedy Method
Approach.
A.2 Prerequisite:
A.3 Outcome:
After successful completion of this experiment students will be able apply greedy
method approach to different problems to find optimal solution and analyze the
complexity of the problem.
A.4 Theory:
The knapsack problem or rucksack problem is a problem in combinatorial
optimization: Given a set of items, each with a weight 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. It derives its
name from the problem faced by someone who is constrained by a fixed-size
knapsack and must fill it with the most valuable items. The problem often arises
in resource allocation where there are financial constraints and is studied in
fields such as combinatorics, computer science, complexity theory, cryptography,
applied mathematics, and daily fantasy sports. Based on the nature of the items,
Knapsack problems are categorized as
- Fractional Knapsack
- 0/1 Knapsack
Fractional Knapsack
In this case, items can be broken into smaller pieces, so that fraction of item can
be selected. According to the problem statement,
There are n items.
th
Weight of i item wi>0
Profit for ith item pi>0 and
Capacity of the Knapsack is W
In this version of Knapsack problem, items can be broken into smaller piece i.e.
fraction xi of ith item.
The ith item contributes the weight xi.wi. to the total weight in the knapsack and
profit xi.pi to the total profit.
Hence, the objective of this algorithm is to
Subject to constraint
It is clear that an optimal solution must fill the knapsack exactly, otherwise we
could add a fraction of one of the remaining items and increase the overall profit.
Thus, an optimal solution can be obtained by
In this context, first we need to sort those items according to the value of pi/wi so
that
Time Complexity:
If the provided items are already sorted into a decreasing order of pi/wi, then the
while loop takes a time in O(n); Therefore, the total time including the sort is in O(n
logn).
PART B
(PART B : TO BE COMPLETED BY STUDENTS)
(Students must submit the soft copy as per following segments within two hours of the
practical. The soft copy must be uploaded on the Blackboard or emailed to the concerned lab
in charge faculties at the end of the practical in case the there is no Black board access
available)
Roll No.: B-36 Name: Mahesh Suresh Bhosale
Class: SE-B COMPS Batch:B2
Date of Experiment: Date of Submission
Grade:
B.1 Software Code written by student:
KNAPSACK CODE:
#include<stdio.h>
#include<conio.h>
void main ()
{
int n, m, w[100], p[100], ratio[100] , i, j, u, temp;
float xr, x[100], total_profit=0, total_weight=0;
clrscr();
printf ("Enter the number of items(n): ");
scanf ("%d", &n);
printf ("Enter the capacity of the Knapsack(m): ");
scanf ("%d", &m);
u = m;
for(i=0;i<n;i++)
{
x[i]=0;
}
printf ("Enter the Weights of items: ");
for (i = 0; i < n; i++)
{
printf ("\n\tWeight of item %d = ", i + 1);
scanf ("%d", &w[i]);
}
printf ("\nEnter the Profit Values of items: ");
for (i = 0; i < n; i++)
{
printf ("\n\tProfit of item %d = ", i + 1);
scanf ("%d", &p[i]);
}
for (i = 0; i < n; i++)
{
ratio[i] = p[i] / w[i];
}
for (i = 0; i < n; i++)
{
for (j = 0; j < n - 1; j++)
{
if (ratio[j] < ratio[i])
{
temp = ratio[i];
ratio[i] = ratio[j];
ratio[j] = temp;
temp = w[i];
w[i] = w[j];
w[j] = temp;
temp = p[i];
p[i] = p[j];
p[j] = temp;
}
}
}
printf("\n The Table After Sorting based on the Ratio: \n");
printf("\nItem:\t\t");
for(i=0;i<n;i++)
{
printf("%d\t",i+1);
}
printf("\nProfit:\t\t");
for(i=0;i<n;i++)
{
printf("%d\t",p[i]);
}
printf("\nWeights:\t");
for(i=0;i<n;i++)
{
printf("%d\t",w[i]);
}
printf ("\nRATIO:\t\t");
for (i = 0; i < n; i++)
{
printf ("%d\t", ratio[i]);
}
for(i=0;i<n;i++)
{
if(w[i]<=u)
{
x[i]=1;
u=u-w[i];
}
else if(w[i]>u)
{
break;
}
}
if(i<=n)
{
xr = (float)u/w[i];
x[i] = xr;
}
printf("\n X = [");
for(i=0;i<n;i++)
{
printf("%.3f , ",x[i]);
}
printf("]");
for(i=0;i<n;i++)
{
total_profit += x[i]*p[i];
total_weight += x[i]*w[i];
}
printf("\nTotal Profit = %.2f \n Total Weight = %.2f
",total_profit,total_weight);
getch();
}
B.2 Input and Output:
B.3 Observations and learning:
Observation: The greedy approach for the Knapsack Problem involves selecting items based on a certain
criteria, such as maximizing value or minimizing weight, at each step without considering the overall
consequences. This approach may not always produce the optimal solution, but it can be efficient for
certain cases.
Learning: Implementing the Knapsack Problem using the greedy method requires careful consideration of
the criteria used to select items. While it may provide a solution quickly, it's important to remember that it
may not always result in the best solution. Understanding the trade-offs between efficiency and optimality
is key when applying greedy algorithms to optimization problems like the Knapsack Problem.
B.4 Conclusion:
In conclusion, implementing the Knapsack Problem using the Greedy Method Approach demonstrates its
efficiency in selecting items based on certain criteria. However, its limitations in always producing the
optimal solution underscore the importance of considering alternative approaches for more complex
scenarios. This experiment provides valuable insights into algorithmic trade-offs and the balance
between simplicity and optimality in optimization problems.
B.5 Question of Curiosity
************************
