Jump to content
usermanero

Problema otimização

Recommended Posts

usermanero

Olá, tenho o seguinte problema a ser resolvido:

Tenho que derrotar um monstro com uma certa quantidade de pontos de vida (HP). Posso utilizar N feitiços, cada um gasta uma quantidade X de mana. Não posso repetir nenhum feitiço.

Qual a quantidade minima de mana que eu posso gastar para conseguir derrotar o monstro?

Exemplo:

3 Feitiços, 10 HP
Feitiço 1 - 5 de dano de HP, 30 de mana
Feitiço 2- 2 de dano de HP, 20 de mana
Feitiço 3 - 6 de dano de HP, 40 de mana

A resposta para esse exemplo é 70 de mana. Ou seja, utilizar os feitiços 1 e 3.

Fiz esse algoritmo, mas ele não funciona em todos os casos que testei. Alguma ajuda por favor.

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


int comparaMana(const void *x, const void *y);
int comparaDano(const void *x, const void *y);

typedef struct spell{
        int dano;
        int mana;
   }Spell;

int main()
{
   int numFeiticos, hp, i, sum=0, sum2=0, sumM=0, sumM2=0;

   while(scanf("%d %d", &numFeiticos, &hp) != EOF){

       Spell v[numFeiticos];

       for(i=0; i<numFeiticos; i++){
            scanf("%d %d", &v[i].dano, &v[i].mana);
            sum += v[i].dano;
            sumM += v[i].mana;
       }

       if(sum<=hp){ //caso seja impossivel derrotar demogorgon ou tenha que usar todos os feitiços
            if(sum==hp){
               printf("%d\n", sumM);
            }
            else{
                printf("-1");
            }
       }
       else{
            sum=0;
            sumM=0;
            sum2=0;
            sumM2=0;
            qsort(v, numFeiticos, sizeof(Spell), comparaMana); //primeiro ordeno por mana e pego sempre a menor quantidade até derrotar monstro

            for(i=0; i<numFeiticos; i++){
                sum += v[i].dano;
                sumM += v[i].mana;
                if(sum >= hp){
                    break;
                }
            }

            qsort(v, numFeiticos, sizeof(Spell), comparaDano); //ordeno por dano e pego sempre maior dano ate derrotar monstro

            for(i=0; i<numFeiticos; i++){
                sum2 += v[i].dano;
                sumM2 += v[i].mana;
                if(sum2 >= hp){
                    break;
                }
            }

            if(sumM > sumM2){
                printf("%d\n", sumM2);
            }
            else{
                printf("%d\n", sumM);
            }
        }
    }
    return 0;
}

int comparaMana(const void *x, const void *y){
    Spell *p1 = (Spell *)x;
    Spell *p2 = (Spell *)y;
    if(p1->mana == p2->mana){
        return 0;
    }
    else{
        if(p1->mana < p2->mana){
            return -1; //p1 vem antes de p2
        }
        else{
            return 1; //p1 vem depois de p2
        }
    }
}

int comparaDano(const void *x, const void *y){
    Spell *p1 = (Spell *)x;
    Spell *p2 = (Spell *)y;

    if(p1->dano == p2->dano){
        return 0;
    }
    else{
        if(p1->dano < p2->dano){
            return 1; //p2 vem antes de p1
        }
        else{
            return -1; //p2 vem depois de p1
        }
    }
}

 

Share this post


Link to post
Share on other sites
HappyHippyHippo

resolução :

- obter todas as permutações dos feitiços

- determinar quals dessas permutações chega primeiro ao valor de hp no seu valor acumulado


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
usermanero
12 horas atrás, HappyHippyHippo disse:

resolução :

- obter todas as permutações dos feitiços

- determinar quals dessas permutações chega primeiro ao valor de hp no seu valor acumulado

Sim, essa seria uma resolução, mas esse seria um algoritmo exponencial não? Porque tem um tempo limite que o meu programa tem que dar uma resposta e geralmente esses algoritmos extrapolam o tempo com entradas muito grandes.

Share this post


Link to post
Share on other sites
HappyHippyHippo

optimizaçáo ?

existem maneiras de "criar" uma pesquisa por essas permutaçóes de forma inteligente, o que tornaria o algoritmo mais eficiente, tipo:

- ordenar as magias por ordem ascendente de custo

- por cada magia da lista "parcial" verificar se a magia é suficiente

- se náo for suficiente, adicionar a pesquisa recursiva do resto da lista

- verificar se o valor calculado é o mínimo do ciclo de verificaçáo

 

sei que o que escrevi é um pouco "abstracto", mas mas do que isso é colocar código ... (se bem que o tenho à minha frente)


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.