Knapsack Problem using Dynamic Programming in C
Here you will get a program code to solve the 0/1 knapsack problem using dynamic programming in C programming language.
How to solve Knapsack Problem using Dynamic programming
The Knapsack Problem using Dynamic Programming is an algorithmic problem, that is used to finding the maximum value. It can be obtained by selecting a combination of items with given weights and values to fit into a knapsack with a limited weight capacity.
Let’s implement a C program that solves the 0/1 Knapsack Problem using Dynamic Programming:
Example of knapsack problem using dynamic programming in C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | //0/1 Knapsack Problem using Dynamic programming in c #include<stdio.h> int max(int x, int y) { return (x > y)? x : y; } int knapSack(int W, int wt[], int val[], int n) { int i, w; int K[n+1][W+1]; for (i = 0; i <= n; i++) { for (w = 0; w <= W; w++) { if (i==0 || w==0) K[i][w] = 0; else if (wt[i-1] <= w) K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]); else K[i][w] = K[i-1][w]; } } return K[n][W]; } int main() { int n,we; printf("Enter the max weight:\n"); scanf("%d",&we); printf("\nEnter the number of items:\n"); scanf("%d",&n); int wt[n],val[n]; printf("\nEnter the weight of each item:\n"); for(int i=0;i<n;i++) scanf("%d",&wt[i]); printf("\nEnter the value of each item:\n"); for(int i=0;i<n;i++) scanf("%d",&val[i]); int val_returned = knapSack(we, wt, val, n); printf("\nThe maximum value is %d\n",val_returned); return 0; } |
Output
Read Also
Implement N Queens Problem using Backtracking
Knapsack Problem Using Greedy Solution
Find Minimum Spanning Tree using Kruskal’s Algorithm