Hello
i'm just trying to do some basic example of dynamic programming and i've an issue with the following code:
Code:
#include <cstdio>
#include <vector>
#include <ctime>
using namespace std;
int cut_rod(vector<int>p,int l){
int m;
if (l==0) return 0;
int q=-32768;
for (int i=1;i<=p.size();i++){
if ((l-i)<0) continue;
m=p[i-1]+cut_rod(p,l-i);
if (q<m) q=m;
}
return q;
}
int main(){
int n,t;
int tstart;
int tend;
tstart=clock();
scanf("%i %i\n ",&n,&t);
int q;
int l;
vector<int> p;
for (int j=0;j<n;j++){
p.push_back(0);
scanf("%i",&p[j]);
}
for (int i=0;i<t;t++){
scanf("%i",&l);
q=cut_rod(p,l);
printf("Case %i: %i \n",i,q);
}
tend=clock();
printf("Elapsed time : %i",tend-tstart);
return 0;
}
The program go crazy also for examples with few iteration like:
What's the problem?