Advertisement
naeem043

C DP Knapsack Problem

Jul 27th, 2018
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 0.61 KB | None | 0 0
  1.  
  2. #include<stdio.h>
  3.  
  4. int max(int a, int b)
  5.  {
  6.       return (a > b)? a : b;
  7.   }
  8.  
  9. int main()
  10. {
  11.     int val[] = {12,10,20,15};
  12.     int wt[] = {2,1,3,2};
  13.     int i, j;
  14.     int K[5][6];
  15.  
  16.        for (i = 0; i <= 4; i++)
  17.        {
  18.            for (j = 0; j <= 5; j++)
  19.            {
  20.                if (i==0 || j==0)
  21.                    K[i][j] = 0;
  22.                else if (wt[i-1] <= j)
  23.                      K[i][j] = max(val[i-1] + K[i-1][j-wt[i-1]],  K[i-1][j]);
  24.                else
  25.                      K[i][j] = K[i-1][j];
  26.            }
  27.        }
  28.     printf("Your Profit = %d", K[4][5]);
  29.  
  30.     return 0;
  31. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement