TLE ! How to optimize this knapsack problem?

help
, , ,
1

This recursive solution is giving TLE. How to optimize it further?
It’s a classic 0-1 Knapsack Problem.
Problem → CSES - Book Shop

CODE

long long n, x;
int price[1000];
int pages[1000];

long long knap(long long n, long long x){
    if(n<=0) return 0;
    if(x<=0) return 0;
    if(price[n-1] > x) return knap(n-1, x);

    else return max(pages[n-1]+knap(n-1, x-price[n-1]), knap(n-1, x));
}

int main(){

    cin>>n>>x;

    for(int i=0; i<n; i++) cin>>price[i];
    for(int i=0; i<n; i++) cin>>pages[i];

    cout<<knap(n, x)<<endl;

    return 0;
}
2

You have neatly formulated the recurrence relation but didn’t notice that your program does repeated calculations.

Hint 1:

Memoization ?

DP

Knapsack problem

1 Like
3

Got it. Thanks :slight_smile: