TOPIC

TLE - Subset-Sum e mínimo de mana

Felipe Fonseca Rocha asked 4 years ago

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

#define MAX 2001
#define true 1
#define false 0
#define bool short

typedef struct{
  int dano,mana;
}feitico;

int manatotal=1000;
bool dp[MAX][MAX];

void printSubsetsRec(feitico* arr, int i, int sum,int soma)
{
    if (i == 0 && sum != 0 && dp[0][sum])
    {
    soma += arr[i].mana;      
    if(soma<manatotal)manatotal=soma;
        return;
    }

    if (i == 0 && sum == 0)
    {
    if(soma<manatotal)manatotal = soma;
        return;
    }

    if (dp[i-1][sum])
    {
      int soma2 = soma;
      printSubsetsRec(arr, i-1, sum, soma2);
    }

    if (sum >= arr[i].dano && dp[i-1][sum-arr[i].dano])
    {
      soma+=arr[i].mana;
      printSubsetsRec(arr, i-1, sum-arr[i].dano,soma);
    }
}

bool printAllSubsets(feitico* arr, int n, int sum)
{
    int i,j;
    if (n == 0 || sum < 0)
       return false;

    for ( i = 1; i < n; ++i){
    dp[i][0] = true;
        for ( j = 0; j < sum + 1; ++j) dp[i][j] = 0;
    }

    if (arr[0].dano <= sum)
       dp[0][arr[0].dano] = true;

    for ( i = 1; i < n; ++i)
        for ( j = 0; j < sum + 1; ++j)
            dp[i][j] = (arr[i].dano <= j) ? dp[i-1][j] || dp[i-1][j-arr[i].dano] : dp[i - 1][j];
    if (dp[n-1][sum] == false)
    return false;

    int soma = 0;
    printSubsetsRec(arr, n-1, sum, soma);
    return true;
}
int main(void)
{
  int i,qtdFeit,vida,aux;

  scanf("%d %d",&qtdFeit,&vida);

  feitico feiticos[MAX];
  aux = 0;
  for(i = 0 ; i < qtdFeit ; i++){
    scanf("%d %d",&feiticos[i].dano,&feiticos[i].mana);
    aux+=feiticos[i].dano;
  }
  if(aux < vida)
    printf("-1\n");
  for(i = 0;i < 10 && !(printAllSubsets(feiticos,qtdFeit,vida+i));i++);
    printf("%d\n",manatotal);

  return 0;
}

TLE - Usei todas as somas que pondem levar dano >= a vida, com mínimo de mana. Não entendi outra forma de modelar o problema.

Poderiam me ajudar?

Remember not post solutions. Your post may be reviewed by our moderators.

  • Semar Augusto replied 4 years ago

    uma outra forma de modelar é usando o problema da mochila modificado. você tem que achar o menor custo para colocar pelo menos k kg lá dentro. http://www.geeksforgeeks.org/minimum-cost-to-fill-given-weight-in-a-bag/