Paradigms

Problema 1310 (LUCRO)

Descrição

George é dono de um circo e traz seu circo de cidade em cidade. Ele sabe o quanto de receita ele pode obter em qualquer dia de uma série de dias em uma cidade. Ele também sabe o custo constante diário para manter o seu circo. George quer trazer seu circo à cidade para a série de dias que resulta em maior lucro.

Por exemplo, se em uma determinada cidade o custo for de $ 20 por dia em um exemplo com 6 dias, sendo que as receitas previstas por dia são {$ 18, $ 35, $ 6, $ 80, $ 15, $ 21}, George pode obter o máximo de lucro trazendo o seu circo para esta cidade do dia 2 ao dia 4. Desta forma ele pode lucrar (35 + 80 + 6) - (3 * 20) = $ 61.

Nota: A série de dias de George traz seu circo para a cidade pode ser entre 0 e o número máximo de dias, inclusive. Obviamente, se George traz seu circo para a cidade por 0 dias, ele obtém $ 0 de lucro.

Entrada

A entrada contém muitos casos de teste. A primeira linha de cada caso de teste contém um inteiro N (1 ≤ N ≤ 50) que representa o número de dias que George pode trazer o seu circo para a cidade. A segunda linha do caso de teste contém um número inteiro custoPorDia (0 ≤ custoPorDia < 1000) que representa o custo em manter o circo na cidade. Segue N linhas (uma por cada dia), contendo cada um um inteiro receita (0 ≤ receita < 1000) representa a receita que o circo obtem em cada dia. O final da entrada é indicado por EOF (fim de arquivo).

Saída

Para cada caso de teste imprima o máximo de dinheiro que George pode ganhar trazendo o seu circo para a cidade de acordo com o exemplo abaixo.

Código

#include <iostream>
using namespace std;

int main()

{

   int N,CPD;

   while(cin>>N>>CPD)
   {
     int i=0,j,R[N],ML=0,L;

     for(int i=0;i<N;i++) cin>>R[i];

     while(i<N)
     {
          if(R[i]>CPD)
          {
               L=0;			
               j=i;
               while(j<N)
               {
                    L=L+R[j]-CPD;
                    if(L>ML)ML=L;
                    j++;
               }			
          }
     i++;					
     }
     cout<<ML<<endl;
   }

}

Problema 1288 (Canhão de Destruição)

Código

   #include <stdio.h>
   #include <stdlib.h>

   int a, a2, b, i, cont;
   int knapsack(int *p, int *v, int n, int c, int *t[], int m)
   {
       m=0;
       cont=0;
       for(b=0;b<=c;b++)
       {
           t[0][b]=0;
           for(i=1;i<=n;i++)
           {
               a=t[i-1][b];
               if(p[i-1]>b)
                   a2=0;
               else a2=t[i-1][b-p[i-1]]+v[i-1];
               t[i][b]=((a>a2)?a:a2);
           }
       }
       b=c;
       for(i=n;i>=1;i--)
           if(t[i][b]!=t[i-1][b])
           {
               m+=v[i-1];
               b=b-p[i-1];
           }
       return m;
   }

   int main ()
   {
       int n, c, m=0, r, num;
       scanf("%d", &num);
       while(num--)
       {
           scanf("%d", &n);
           int p[n], v[n];
           for(cont=0;cont<n;cont++)
               scanf("%d%d", v+cont, p+cont);
           scanf("%d%d",&c,&r);
           int *t[n+1];
           for(cont=0;cont<=n;cont++)
               t[cont]=(int*) malloc((c+1)*sizeof(int));
           m=knapsack(p,v,n,c,t,m);
           (m>=r)?printf("Missao completada com sucesso\n"):printf("Falha na missao\n");
       }
       return 0;
   }

Observações e explicações

Para a resolução do problema foi usado o algoritmo da mochila, que maximiza um valor, dado um conjunto de elementos com um certo valor e peso cada, e um limite para o peso total.

• Referência teórica: http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/mochila-bool.html
• Algoritmo para referência: http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/solucoes/mochila-bool2.html