Book shop dp problem top down dp approach giving tle
my code:
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;const int mod=pow(10,9)+7;
int main()
{int n,x;
int price[1001],pages[1001];
int dp[1005][100005];
memset(dp,0,sizeof(dp));
cin>>n>>x;
for(int i=0;i<n;i++)
{
cin>>price[i];
}
for(int i=0;i<n;i++)
{
cin>>pages[i];
}
for(ll i=0;i<=n;i++)
{
for(ll j=0;j<=x;j++)
{
if(i==0 || j==0)
{
dp[i][j]=0;
}
else
{
break;
}
}
}
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=x;j++)
{if(j-price[i-1]>=0) { dp[i][j]=max(dp[i-1][j-price[i-1]]+pages[i-1],dp[i-1][j]); } else { dp[i][j]=dp[i-1][j]; } }
}
cout<<dp[n][x];
return 0;
}
You’ll have to use iterative DP for this problem. I don’t think there is any other way to get around that Runtime Error “RecursionError: maximum recursion depth exceeded in comparison”.
Its similar to 0/1 knapsack problem.
It is the 0/1 Knapsack problem (in disguise ).
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int MOD=1e9+7;
#define _f .first
#define _s .second
int32_t main() {
int n,x;
cin>>n>>x;
vector<pair<int,int>> books(n+1);
for(int i=1;i<=n;i++){
cin>>books[i]_f;
}
for(int i=1;i<=n;i++){
cin>>books[i]_s;
}
int dp[n+1][x+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=x;j++){
if(i==0||j==0)dp[i][j]=0;
else if(books[i]_f <= j)
dp[i][j] = max(books[i]_s+ dp[i-1][j-books[i]_f], dp[i-1][j]);
else
dp[i][j] = dp[i-1][j];
//cout<<dp[i][j]<<" ";
}
// cout<<"\n";
}
cout<<dp[n][x];
return 0;
}
That is it