Question

The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible value. Using greedy paradigm, we can solve this problem easily. Your task is the following:

(a) Write the pseudo-code of a greedy solution for knapsack problem.

(b) Give is the time complexity of your solution in part (a).

(c) Implement part (a) in C programming language.

Answer 1

Answer-

there are two types of Knapsack problem

-> 0-1 Knapsack

-> Fractional Knapsack

if problem type is Fractional Knapsack then we can apply Greedy Paradigm to optimal solution

Answer (a)

Pseudo-code of a greedy solution for knapsack problem

Greedy_fractional_knapsack (w, v, W) // w is weight of Items , v is value of Items and W is Capacity of Knapsack

FOR i =1 to n
do x[i] =0
weight = 0
while weight < W
do i = best remaining item
IF weight + w[i] ≤ W
then x[i] = 1
   weight = weight + w[i]
else
x[i] = (w - weight) / w[i]
weight = W
return x

Answer (b)  

Time complexity of above Pseudo-code
we keep the items in heap with largest vi/wi at the root. Then creating the heap takes O(n) time
while-loop now takes O(log n) time for extract largest vi/wi each time(since heap property must be restored after the removal of root) this process will happen n times so it will take O(n log n) time

so total Time complexity=O(n)+O(n log n)

=O(n log n)

Answer (c)

C program

# include<stdio.h>

void knapsack(int n, float weight[], float value[], 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 + value[i];
u = u - weight[i];
}
}

if (i < n)
x[i] = u / weight[i];
tp = tp + (x[i] * value[i]);

printf("\nThe result is:- ");
for (i = 0; i < n; i++)
printf("%f\t", x[i]);
printf("\nMaximum value is:- %f", tp);

}


int main()
{
float weight[20], value[20], capacity;
int num, i, j;
float ratio[20], temp;
printf("\nEnter the no. of items:- ");
scanf("%d", &n);
printf("\nEnter the weights and values of each items:- ");
for (i = 0; i < n; i++)
{
scanf("%f %f", &weight[i], &value[i]);
}
printf("\nEnter the capacityacity of knapsack:- ");
scanf("%f", &capacity);
for (i = 0; i < n; i++)
{
ratio[i] = value[i] / weight[i];
}

for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; 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 = value[j];
value[j] = value[i];
value[i] = temp;
}
}
}
  
knapsack(n, weight, value, capacity);

return(0);

}