@chawuciren
2018-11-30T12:46:11.000000Z
字数 976
阅读 685
算法导论
以下是cut rob的c语言实现
#include<stdio.h>
#include<stdlib.h>
int max(int a,int b);//找两个数中最大值的函数
int mcr(int p[]);//这个和mcra配套,计算cut rob的最大利润,可以记忆
int buc(int p[],int n);//更加简洁的记忆版本
int mcra(int p[],int n,int r[]);
void ebucr(int p[],int n);//更加高级的记录过程版本(不知道对不对)
int main(){
int p[11]={0,1,5,8,9,10,17,17,20,24,30};//第一个元素放0,后面会好操作
ebucr(p,11);
return 0;
}
int mcr(int p[]){
int r[11];
for(int i=0;i<11;i++)
r[i]=-100;
return mcra(p,9,r);//修改这里的数字,就可以算不同的总长最大利润(仅限于10以内)
}
int mcra(int p[],int n,int r[]){//
int q;
if(r[n]>=0)
return r[n];
if(n==0){
q=0;
}
else{
q=-1;
for(int i=1;i<=n;i++){
q=max(q,p[i]+mcra(p,n-i,r));
}
}
r[n]=q;
return q;
}
int max(int a,int b){
if(a>=b)
return a;
else
return b;
}
int buc(int p[],int n){
int r[11]={0};
int q=-100;
for(int j=1;j<11;j++){
for(int i=1;i<=j;i++){
q=max(q,p[i]+r[j-i]);
}
r[j]=q;
}
return r[n];
}
void ebucr(int p[],int n){
int r[11]={0};
int s[11]={0};
int q;
r[0]=0;
for(int j=1;j<=n;j++){
q=-100;
for(int i=1;i<=j;i++){
if(q<p[i]+r[j-1]){
q=p[i]+r[j-i];
s[j]=i;
}
}
r[j]=q;
}
for(int i=0;i<n;i++){
printf("%d",r[i]);
printf("%d",s[i]);
}
return;
}