Advertisement
Caio_25

Mochila 0-1

Apr 23rd, 2019
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.14 KB | None | 0 0
  1. #include<stdio.h>
  2.  
  3. typedef struct{
  4.  
  5.     float peso, valor;
  6. }item;
  7.  
  8. void cadastrar_itens(int n, item v[]);
  9. float maior(float a, float b);
  10. float mochila(int n, item v[], float peso_max);
  11.  
  12. int main()
  13. {
  14.     item v[1000];
  15.     int n;
  16.     float peso_max;
  17.    
  18.     printf("Informe a qtd de itens: ");
  19.     scanf("%d", &n);
  20.    
  21.     cadastrar_itens(n, v);
  22.    
  23.     printf("Informe o peso maximo da mochila: ");
  24.     scanf("%f", &peso_max);
  25.    
  26.     printf("O maior valor que a mochila suporta vale: %f\n", mochila(n, v, peso_max));
  27.    
  28. }
  29.  
  30. void cadastrar_itens(int n, item v[])
  31. {
  32.     for(int i = 0; i < n;  i++)
  33.     {
  34.         printf("Informe o peso do item: ");
  35.         scanf("%f", &v[i].peso);
  36.        
  37.         printf("Informe o valor do item: ");
  38.         scanf("%f", &v[i].valor);
  39.     }
  40. }
  41.  
  42. float maior(float a, float b)
  43. {
  44.     if(a > b)
  45.     {
  46.         return(a);
  47.     }
  48.    
  49.     else
  50.     {
  51.         return(b);
  52.     }
  53. }
  54.  
  55. float mochila(int n, item v[], float peso_max)
  56. {
  57.    
  58.     if(n < 0)
  59.     {
  60.         return(0);
  61.     }
  62.    
  63.     else
  64.     {
  65.         if(v[n].peso <= peso_max)
  66.         {
  67.             return(  maior( ( v[n].valor + mochila(n - 1, v, peso_max - v[n].peso)) , (mochila(n-1, v, peso_max))   ) );
  68.         }
  69.        
  70.         else
  71.         {
  72.             return(mochila(n-1, v, peso_max));
  73.         }
  74.     }
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement