How to optimize the solution based on dp

Правка en3, от maverick06, 2020-11-13 12:42:03

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,vector<int>a)
{
	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);
		vector<int>a(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:)

Теги #dynamic programing, 0/1 knapsack, #spoj, #c++

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский maverick06 2020-11-13 12:42:03 16
en2 Английский maverick06 2020-11-13 12:38:58 10
en1 Английский maverick06 2020-11-13 12:38:03 914 Initial revision (published)