TLE в рюкзаке проблема с использованием памятки - PullRequest
Новая
       39

TLE в рюкзаке проблема с использованием памятки

1 голос
/ 27 апреля 2020

Постановка задачи: Учитывая n предметов размером Ai, целое число m обозначает размер рюкзака. Как полно вы можете заполнить этот рюкзак?

Пример Пример 1: Ввод: [3,4,8,5], размер рюкзака = 10 Выход: 9

Пример 2: Ввод: [2 , 3,5,7], размер рюкзака = 12 Вывод: 12

Мне нужно написать решение, используя мемоизацию, я знаю, что снизу вверх дп будет довольно быстрым, Но можете ли вы помочь мне с другой оптимизацией, которую я могу добавить в это решение. 

class Solution {
public:
    unordered_map<string,int>m1;
    int solve(int m,vector<int>&a,int i){
        if(i<0)return 0;

        string s = to_string(m)+" "+to_string(i);
        if(m1.count(s))return m1[s];
        int val=0;
        if(m-a[i]>=0)val = a[i] + solve(m-a[i],a,i-1);
        return m1[s]=max(val,solve(m,a,i-1));

    }
    int backPack(int m, vector<int> &a) {
        // write your code here
       return solve(m,a,int(a.size()-1));
    }
};

1 Ответ

0 голосов
/ 27 апреля 2020

Рассмотрите возможность создания ха sh из двух целых чисел m и i, следуя подходу, подобному this , и используйте его в качестве ключа на карте. Вы должны увидеть улучшение во время выполнения, хотя решение снизу вверх лучше. В вашем коде to_string требует времени, а также ищет больше строки, чем вы думаете, как указано в комментариях.

...