TOPIC

Time Limit Exceeded

Vitor Vilela asked 2 years ago

Qual seria uma maneira melhor de resolver esse problema? Ainda tenho muita pouca experiência em DP mas não consigo pensar em uma tabela menor que dp[150][2000*150+1]

Note que eu também já fez o mesmo código em versão iterativa (sem recursão/função separada) mas o desempenho não melhora.

Grato!!

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

int sum;
int mem[150];
int n;

int cache[150][2000*150+1];

int partSum(int i, int t) {
    if (i == n) {
        return abs(2*t - sum);
    }

    if (cache[i][t] != -1) {
        return cache[i][t];
    }

    int a = partSum(i + 1, t + mem[i]);
    int b = partSum(i + 1, t);
    int r = a < b ? a : b;

    cache[i][t] = r;
    return r;
}

int main() {
    while (scanf("%d", &n) != EOF) {
        int i; sum = 0;
        memset(cache, -1, sizeof(cache));

        for (i = 0; i < n; ++i) {
            scanf("%d", &mem[i]);
            sum += mem[i];
        }

        printf("%d\n", partSum(0, 0));
    }

    return 0;
}

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

  • feodorv replied 2 years ago

    You can apply bottom-up DP, one dimention [150] will go into a cicle. Moreover, for each DP state you need only 1 bit so no need in int dp[...]. Also the limit for the number of DP states is not N X but sum / 2.

  • 🎈🎈 VICTOR 🎈🎈CI73A2019 replied 2 years ago

    To começando achar que esse é um outro tipo de paradigma.. vou pesquisar aqui .. tenho uma idéia

  • 🎈🎈 VICTOR 🎈🎈CI73A2019 replied 2 years ago

    Vixi vitão... já tentei todo tipo de DP pra esse problema kkk hard.. rangel fumou uma colinha