15.1实现

算法导论

以下是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;
}