Here you will learn about 0-1 knapsack problem in C.
If you are interested in learning more about dynamic programming techniques, AlgoMonster’s Dynamic Programming Introduction and Dynamic Programming Patterns.
We are given n items with some weights and corresponding values and a knapsack of capacity W. The items should be placed in the knapsack in such a way that the total value is maximum and total weight should be less than knapsack capacity.
In this problem 0-1 means that we can’t put the items in fraction. Either put the complete item or ignore it. Below is the solution for this problem in C using dynamic programming.
Program for Knapsack Problem in C Using Dynamic Programming
|
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 |
#include<stdio.h> int max(int a, int b) { return (a > b)? a : b; } 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 i, n, val[20], wt[20], W; printf("Enter number of items:"); scanf("%d", &n); printf("Enter value and weight of items:\n"); for(i = 0;i < n; ++i){ scanf("%d%d", &val[i], &wt[i]); } printf("Enter size of knapsack:"); scanf("%d", &W); printf("%d", knapSack(W, wt, val, n)); return 0; } |
Output
Enter number of items:3
Enter value and weight of items:
100 20
50 10
150 30
Enter size of knapsack:50
250
You can watch below video to learn knapsack problem easily.
Source: http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/
thanks , really a grate article.
effective programing
thanks to helpful me !!!!!!
For learning programming, Your website is the best Neeraz.
What does the val array contain?Thanks in advance
this program is not defind in the java using c
int max(int a, int b) { return (a > b)? a : b; }
Require of this line ???
Hey hai , this chandru..
I need an explanation on the condition
1. Else if(wt[i-1]<=w) // this means that weight at index [i-1] is compared with index w
where weight values are [20,10,30 ] and w[0 to n]..
so when comparing wt[i-1]<=w which will never be a true.. If i am right!!!
w is not from 0 to n. w is from 0 to W. here in this case w[0 to 50].
Thanks for this great tutorial. I have tried to change the code, because I need to show the selected Items, but it doesn’t work.
Maybe Someone have a solution that show the chosen items ?
Thanks for help
What if we need to solve it using backtracking approach??
Thank you a lot for the program.
You offer me 2 bonus points on my final exam.
Love on you <3