How to optimize the solution based on dp

Revision en2, by maverick06, 2020-11-13 12:38:58

Here is the link to the problem : https://www.spoj.com/problems/RPLB/

Here is my code however it is giving tle:

include <bits/stdc++.h>

using namespace std; int dp[20001][20001]; int knapsack(int n,int s,vectora) { if(n <= 0 || s<0) { return 0; } if(dp[n][s]!=-1) { return dp[n][s]; } if(a[n-1]<=s) { return dp[n][s] = max(a[n-1]+knapsack(n-2,s-a[n-1],a),knapsack(n-1,s,a)); } else { return dp[n][s] = knapsack(n-1,s,a); } }

int main() { // your code goes here int t; scanf("%d",&t); for(int i=1;i<=t;i++) { int n,s; scanf("%d%d",&n,&s); vectora(n); for(int i=0;i<n;i++) { int num; scanf("%d",&num); a[i] = num; } memset(dp,-1,sizeof(dp)); int ans = knapsack(n,s,a); //cout<<ans<<endl; printf("Scenario #%d: %d\n",i,ans); } }

Thanks:)

Tags #dynamic programing, 0/1 knapsack, #spoj, #c++

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English maverick06 2020-11-13 12:42:03 16
en2 English maverick06 2020-11-13 12:38:58 10
en1 English maverick06 2020-11-13 12:38:03 914 Initial revision (published)