rod cutting problem
#include <bits/stdc++.h>
using namespace std;
class item
{
public:
int length;
int price;
void init(int a,int b)
{
length=a;
price=b;
}
};
int solve(int n,item arr[])
{
int dp[n+1][n+1];
for(int i=0;i<=n;i++)
{
dp[0][i]=0;
dp[i][0]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(arr[i-1].length<=j)
{
dp[i][j]=max((arr[i-1].price+dp[i][j-arr[i-1].length]),dp[i-1][j]);
}
else
{
dp[i][j]=dp[i-1][j];
}
}
}
return dp[n][n];
}
int main()
{
int n;
cin>>n;
item arr[n];
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
arr[i].init(a,b);
}
cout<<solve(n,arr);
return 0;
}