Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int w[10], p[10], v[10][10], n, i, j, capacity, x[10] = {0};
  5.  
  6. int max(int i, int j) {
  7.     return ((i > j) ? i : j);
  8. }
  9.  
  10. int KnapSack(int i, int j) {
  11.     int value;
  12.     if (v[i][j] < 0) {
  13.         if (j < w[i])
  14.             value = KnapSack(i - 1, j);
  15.         else
  16.             value = max(KnapSack(i - 1, j), p[i] + KnapSack(i - 1, j - w[i]));
  17.         v[i][j] = value;
  18.     }
  19.     return (v[i][j]);
  20. }
  21.  
  22. int main(int argc, char** argv) {
  23.     int profit, count = 0;
  24.     printf("\nEnter the number of elements : ");
  25.     scanf("%d", &n);
  26.     printf("\nEnter the profit and weights of the elements\n");
  27.     for (i = 1; i <= n; i++) {
  28.         printf("Item no : %d\n", i);
  29.         scanf("%d %d", &p[i], &w[i]);
  30.     }
  31.     printf("\nEnter the capacity \n");
  32.     scanf("%d", &capacity);
  33.     for (i = 0; i <= n; i++)
  34.         for (j = 0; j <= capacity; j++)
  35.             if ((i == 0) || (j == 0))
  36.                 v[i][j] = 0;
  37.             else
  38.                 v[i][j] = -1;
  39.     profit = KnapSack(n, capacity);
  40.     i = n;
  41.     j = capacity;
  42.     while (j != 0 && i != 0) {
  43.         if (v[i][j] != v[i - 1][j]) {
  44.             x[i] = 1;
  45.             j = j - w[i];
  46.             i--;
  47.         } else
  48.             i--;
  49.     }
  50.     printf("Items in the KnapSack are : \n\n");
  51.     printf("Sl.no \t weight \t profit\n");
  52.     printf("\n----------------------------------------\n");
  53.     for (i = 1; i <= n; i++)
  54.         if (x[i])
  55.             printf("%d \t %d \t\t  %d\n", ++count, w[i], p[i]);
  56.     printf("Total profit = %d\n", profit);
  57.     return (EXIT_SUCCESS);
  58. }
  59.  
  60.  
  61. /*
  62.  
  63. Output:-
  64.  
  65. Enter the number of elements : 3
  66.  
  67. Enter the profit and weights of the elements
  68. Item no : 1
  69. 4 6
  70. Item no : 2
  71. 1 2
  72. Item no : 3
  73. 7 3
  74.  
  75. Enter the capacity
  76. 7
  77. Items in the KnapSack are :
  78.  
  79. Sl.no    weight          profit
  80.  
  81. ----------------------------------------
  82. 1        2                1
  83. 2        3                7
  84. Total profit = 8
  85.  
  86.  
  87. */