Knapsack Problem C Program and explanation by Nived Kannada |
The knapsack problem is a very interesting type of problem in computer science. It relates a usual computer science problem with the real-life application of filling a knapsack with items or objects in the most efficient way possible while solving the computer science counterpart of the same problem.
It might sound like a complex algorithm. But actually, it is very easy to learn and understand. So, in this article, we are going to see how to implement the Knapsack problem using C Programming along with its explanation. Literally, each part of the code is commented, so you can clearly get an idea of how it works.
The logic is very simple!
Imagine that you have a Knapsack of capacity m. If you have n objects in your hand and each object is associated with a profit value and a weight value, and you want to fill these objects into the knapsack in the most efficient/profitable way possible. This is basically what we call a knapsack problem.
The logic is as follow,
- Read number of items to variable n
- Read capacity of knapsack to variable m
- Initialize remaining capacity of the knapsack as u=m (initially remaining capacity is full capacity)
- Initialize solution array x[] with value 0 in indices 0 to n-1
- Read the weights and profits of each item into two separate arrays w[] and p[]
- Find the Pi/Wi ratio of each item and store in array ratio[]
- Sort the ratio[] array in its descending order. Rearrange the corresponding values in other arrays p[] and w[] along with it.
- Display the sorted table (Print the arrays p[] ,w[] and ratio[])
- Calculate Solution array x[]
For each weight in w[] that is less than or equal to the value of u (ie. remaining capacity),
set x[i] = 1 and set reduce the value of u by the weight value w[i] (ie. u=u-w[i])
if w[i] becomes greater than u then simply break out of the loop and check whether i is less than or equal to n. If i<=n then simply calculate u/w[i] and store it in a variable xr - Display the solution array x[]
- Calculate total profit and total weight by simply multiplying and accumulating x[i]*p[i] and x[i]*w[i]
- Display the Total profit and Total weight
Web Design for Beginners in Malayalam - Full Course (മലയാà´³ം)
WATCH VIDEO
Open in OnlineGDB
//C Program to Simulate KnapSack Problem // Code by Nived Kannada #include<stdio.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; //Reading number of items printf ("Enter the number of items(n): "); scanf ("%d", &n); //Reading the capacity of the knapsack printf ("Enter the capacity of the Knapsack(m): "); scanf ("%d", &m); //Initializing remaining capacity of Knapsack (u) u = m; //Initializing Solution Array x[] for(i=0;i<n;i++) { x[i]=0; } //Reading the Weights printf ("Enter the Weights of items: "); for (i = 0; i < n; i++) { printf ("\n\tWeight of item %d = ", i + 1); scanf ("%d", &w[i]); } //Reading the Profit values 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]); } //Calculating Pi/Wi ratio of each item and storing in array ratio[] for (i = 0; i < n; i++) { ratio[i] = p[i] / w[i]; } //Sorting all the arrays based on the ratio in descending order 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; } } } //PRINTING THE SORTED TABLE printf("\n The Table After Sorting based on the Ratio: \n"); //Printing Item numbers printf("\nItem:\t\t"); for(i=0;i<n;i++) { printf("%d\t",i+1); } //Printing Profit Array printf("\nProfit:\t\t"); for(i=0;i<n;i++) { printf("%d\t",p[i]); } //Printing Weight Array printf("\nWeights:\t"); for(i=0;i<n;i++) { printf("%d\t",w[i]); } //Printing RATIO Array printf ("\nRATIO:\t\t"); for (i = 0; i < n; i++) { printf ("%d\t", ratio[i]); } //Calculating Solution Array x for(i=0;i<n;i++) { if(w[i]<=u) { x[i]=1; //Setting solution index as 1 u=u-w[i]; //updating remaining knapsack capacity } else if(w[i]>u) { break; } } if(i<=n) { xr = (float)u/w[i]; //Calculating what fraction of that item will fit into the knapsack x[i] = xr; //Setting this fraction to solution array } //Printing Solution Array x printf("\n X = ["); for(i=0;i<n;i++) { printf("%.3f , ",x[i]); } printf("]"); //Calculating Total Profit & Total Weight for(i=0;i<n;i++) { total_profit += x[i]*p[i]; total_weight += x[i]*w[i]; } //Displaying Total Profit and Total Weight printf("\nTotal Profit = %.2f \n Total Weight = %.2f ",total_profit,total_weight); } //End of Code //Code by Nived Kannada // www.nanogalaxy.org
Sample Output
If you found this article helpful, please let us know in the comments below. If you found any errors in the code or the logic, please let us know. We are always happy to help. Thanks!
Articles You Might Like
- C Program to Simulate C-LOOK Disk Scheduling Algorithm | Logic Explained
- C Program to Simulate LOOK Disk Scheduling Algorithm | Logic Explained
- C Program to Simulate C-SCAN Disk Scheduling Algorithm | Logic Explained
- C Program to Simulate SCAN (Elevator) Disk Scheduling Algorithm in OS | Program Logic Explained
- C Program to Simulate Banker's Algorithm | Explicitly Commented(Easy to Understand)
- C Program to Simulate Round Robin CPU Scheduling Algorithm (With Detailed Comments - Simplest Method)
- C Program to Simulate Priority Scheduling Algorithm (With proper comments to easily understand the logic)
- C Program to Simulate Shortest Job First (SJF) CPU Scheduling Algorithm (With Proper Comments to Understand the Logic)
- C Program to Simulate FCFS CPU Scheduling Algorithm (With Proper Comments to Understand the Logic)
No comments:
Post a Comment