fork download
copy 
  1. /* 0-1 Knapsack problem:
  2. - Problem: Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).
  3. - Solution: Consider all subsets of items and calculate the total weight and value of all subsets. Consider the only subsets whose total weight is smaller than W. From all such subsets, pick the maximum value subset.
  4. To consider all subsets of items, there can be two cases for every item: 
  5. 1. the item is included in the optimal subset. 
  6. 2. not included in the optimal set.
  7. Therefore, the maximum value that can be obtained from n items is max of following two values.
  8. 1) Maximum value obtained by n-1 items and W weight (excluding nth item).
  9. 2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).
  10. If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.
  11. */
  12. #include<stdio.h>
  13.  
  14. int knapsackRec(int W, int wt[], int val[], int n);
  15. int knapSackDP(int W, int wt[], int val[], int n);
  16. int max(int a, int b);
  17.  
  18. int main()
  19. {
  20.     int val[] = {60, 100, 120};
  21.     int wt[] = {10, 20, 30};
  22.     int  W = 50;
  23.     int n = sizeof(val)/sizeof(val[0]);
  24.     printf("Rec: Max value for weight=%d is: %d",W,knapsackRec(W, wt, val, n));
  25. 	printf("DP: Max value for weight=%d is: %d",W,knapsackDP(W, wt, val, n));
  26.     return 0;
  27. }
  28.  
  29. int knapSackDP(int W, int wt[], int val[], int n)
  30. {
  31.    int i, w;
  32.    int K[n+1][W+1];
  33.  
  34.    // Build table K[][] in bottom up manner
  35.    for (i = 0; i <= n; i++)
  36.    {
  37.        for (w = 0; w <= W; w++)
  38.        {
  39.            if (i==0 || w==0)
  40.                K[i][w] = 0;
  41.            else if (wt[i-1] <= w)
  42.                  K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
  43.            else
  44.                  K[i][w] = K[i-1][w];
  45.        }
  46.    }
  47.  
  48.    return K[n][W];
  49. }
  50.  
  51. // Knapsack Problem Recursive implementation
  52. // Time complexity: 2^n (Exponential).
  53. int knapsackRec(int W, int wt[], int val[], int n)
  54. {
  55.    // Base Case
  56.    if (n == 0 || W == 0)
  57.        return 0;
  58.  
  59.    // If weight of the nth item is more than Knapsack capacity W, then this item cannot be included in the optimal solution
  60.    if (wt[n-1] > W)
  61.        return knapsackRec(W, wt, val, n-1);
  62.  
  63.    // Return the maximum of two cases: 
  64.    // (1) nth item included 
  65.    // (2) not included
  66.    else 
  67. 	   return max(val[n-1]+knapsackRec(W-wt[n-1],wt,val,n-1),knapsackRec(W,wt,val,n-1));
  68. }
  69.  
  70. int max(int a, int b) 
  71. { 
  72. 	return (a > b)? a : b; 
  73. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c: In function 'main':
prog.c:25:48: warning: implicit declaration of function 'knapsackDP' [-Wimplicit-function-declaration]
  printf("DP: Max value for weight=%d is: %d",W,knapsackDP(W, wt, val, n));
                                                ^
/home/nG6vgv/ccg9T8ir.o: In function `main':
prog.c:(.text.startup+0x65): undefined reference to `knapsackDP'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/53LdmV
language:
C (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!