0/1 knapsack problem using dynamic programming in C
Here you will learn the example code of 0/1 knapsack problem using dynamic programming in C language.
Example code of 0/1 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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | #include<stdio.h> #include<conio.h> #define MAX 20 void knapsackLK(int,int); int max(int,int); void backtracking(); int weight[MAX],value[MAX],W,no,*x; int v[MAX][MAX]; main() { int i,j; printf("\n Enter number of Object you want:"); scanf("%d",&no); printf("\n Enter weight and values in ascending order of vales");; for(i=1;i<=no;i++) { printf("\n Enter Weight and Value for Object %d:",i); scanf("%d %d",&weight[i],&value[i]); } printf("\n Enter knapsack Capacity:"); scanf("%d",&W); knapsackLK(no,W); backtracking(); getch(); } void knapsackLK(int no,int W) { int i,j; for(i=0;i<= W ;i++) v[0][i]=0; for(i=0;i<= no;i++) v[i][0]=0; for(i=1;i<= no;i++) { for(j=1;j<= W;j++) { if((j-weight[i])< 0) v[i][j]=v[i-1][j]; else v[i][j]=max(v[i-1][j],v[i-1][j-weight[i]]+value[i]); } } printf("\n \t "); for(i=0;i<= W;i++) printf("%2d ",i); printf("\n-----------------------------------------------------------------------------"); for(i=0;i<=no;i++) { printf("\n w%d=%2d v%d=%2d |",i,weight[i],i,value[i]); for(j=0;j<= W;j++) printf("%2d ",v[i][j]); } printf("\n-----------------------------------------------------------------------------"); printf("\n Maximum value carry by knapsack is:%2d",v[no][W]); printf("\n-----------------------------------------------------------------------------"); } int max(int a,int b) { return (a >b)?a:b; } void backtracking() { int j1,i; j1=W; printf("\nIncluded Object \t weight \t value"); printf("\n-----------------------------------------------------------------------------"); for(i=no;i >=0;i--) { if(v[i][j1]!=v[i-1][j1] && (v[i][j1]==v[i-1][j1-weight[i]]+value[i])) { printf("\n%2d \t\t\t %2d \t\t %2d",i,weight[i],value[i]); j1=j1-weight[i]; } } } |
Output
Read Also
Implement N Queens Problem using Backtracking
Knapsack Problem Using Greedy Solution
1/2 Knapsack Problem Using Dynamic Programming in C