Experiment No: 06
1. Experiment vision:Write a program to study and implement Knapsack
problem.
2. OBJECTIVE: Program to implement Knapsack problem in c program.
3.
THEORY: The knapsack problem or rucksack problem is
a problem in combinatorial optimization: Given a set of items, each with a mass
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.
- 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 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 useful items.
4. PROGRAM:
#
include<stdio.h>
void
knapsack(int n, float weight[], float profit[], float capacity) {
float x[20], tp = 0;
int i, j, u;
u = capacity;
for (i = 0; i < n; i++)
x[i] = 0.0;
for (i = 0; i < n; i++) {
if (weight[i] > u)
break;
else {
x[i] = 1.0;
tp = tp + profit[i];
u = u - weight[i];
}
}
if (i < n)
x[i] = u / weight[i];
tp = tp + (x[i] * profit[i]);
printf("\nthe result vector is:-
");
for (i = 0; i < n; i++)
printf("%f\t", x[i]);
printf("\nmaximum profit is:- %f",
tp);
}
int
main() {
float weight[20], profit[20], capacity;
int num, i, j;
float ratio[20], temp;
printf("\nenter the no. of objects:-
");
scanf("%d", &num);
printf("\nenter the wts and profits of
each object:- ");
for (i = 0; i < num; i++) {
scanf("%f %f", &weight[i],
&profit[i]);
}
printf("\nenter the capacityacity of
knapsack:- ");
scanf("%f", &capacity);
for (i = 0; i < num; i++) {
ratio[i] = profit[i] / weight[i];
}
for (i = 0; i < num; i++) {
for (j = i + 1; j < num; j++) {
if (ratio[i] < ratio[j]) {
temp = ratio[j];
ratio[j] = ratio[i];
ratio[i] = temp;
temp = weight[j];
weight[j] = weight[i];
weight[i] = temp;
temp = profit[j];
profit[j] = profit[i];
profit[i] = temp;
}
}
}
knapsack(num, weight, profit, capacity);
return(0);
}
5. OUTPUT:
------------------------------------------
------------------------------------------
6. conclusion:
Thus we studied Knapsack problem
and executed successfully.
7. REMARK: The problem often arises
in resource allocation where
there are financial constraints and is studied in fields such as combinatory, computer science, complexity theory, cryptography, applied mathematics,
and daily fantasy sports.
8. Discussion Questions:
1) what
is Knapsack problem?
_________________________________________________________________________________________________________________________________________________________
2) What is Greedy methods?
________________________________________________________________________________________________________________________________________________________
No comments:
Post a Comment