一、问题描述：

有n个底面为长方形的货柜需要租用库房存放，且每个货柜必须放地面上，所有货柜底面宽度都等于库房宽度，则第 i 个货柜占用库房面积大小只需用底面长度L{ i }表示，i=0，1，...，n。设库房总长度为D，第i号货柜存储收益V{ i }。则怎样选择放入的货柜，使库房出租收益最大？

二、递推公式

目标函数：max

约束条件：；

        可得优化函数F[k][y]的递推关系和边界条件：

1.F[k][y]=max{F[k-1][y],F[k][y-L[k]]+V[k]}

2.F[0][y]=0 , 0<=y<=b

3.F[k][0]=0 , 0<=k<=n

4.F[1][y]=[y/L[1]]*V[1]

5.F[k][y]=-Inf  ,y<0

三：代码实现

#include <stdio.h>
#include <stdlib.h>
main()
{
    int n,i,D,k,y,j,w;
    int L[10000],V[10000];
    //L用于储存各柜子长度；V用于储存各柜子储存收益
    printf("请输入规划柜子的种数：\n");
    scanf("%d",&n);
    printf("请输入库房总长度：\n");
    scanf("%d",&D);
    L[0]=V[0]=0;  //让L和V都从1开始计数
    for(i=1;i<=n;i++)
    {
        printf("请输入第%d号柜子底面长度：\n",i);
        scanf("%d",&L[i]);
        printf("请输入第%d号柜子储存收益：\n",i);
        scanf("%d",&V[i]);
    }
    int F[100][100],I[100][100];
    //F用于储存总长不超过y时放入前k种物品的最大收益
    //I用于储存标记函数
    for(k=0;k<=n;k++)  //第0列赋初值0
    {
        F[k][0]=0;
        I[k][0]=0;

    }
    for(y=0;y<=D;y++)  //第0行赋初值0以及第一行赋值
    {
        F[0][y]=0;
        I[0][y]=0;
        F[1][y]=(y/L[1])*V[1];
        if(y/L[1]!=0)
            I[1][y]=1;
        else
            I[1][y]=0;
    }
    for(y=1;y<=D;y++)  //利用F[k][y]=max{F[k-1][y],F[k][y-L[k]]+V[k]}计算F以及I
    {
        for(k=2;k<=n;k++)
        {
            if(y-L[k]<0||F[k-1][y]>(F[k][y-L[k]]+V[k]))
            {
                F[k][y]=F[k-1][y];
                I[k][y]=I[k-1][y];
            }
            else
            {
                F[k][y]=F[k][y-L[k]]+V[k];
                I[k][y]=k;
            }
        }
    }

    int x[100];  //x来记录每个柜子应该放的个数
    for(j=1;j<=n;j++)
    {
        x[j]=0;  //赋初值0
    }
    y=D;
    j=n;
    do
    {
        j=I[j][y];  //从标记函数I的最后一行最后一列开始读
        x[j]=1;    //最后一行允许放入的最大标记物品更新值为1
        y=y-L[j];  //允许最大长度变为以前长度减去已放入的物品长度
        while(I[j][y]==j) //假如更新后的最大长度允许放入的最大标记数量仍然等于j，则j的数量继续增加
        {
            y=y-L[k];
            x[j]=x[j]+1;
        }
    }while(I[j][y]!=0);  //直到标记函数读完，不再允许任何物品放入
    w=F[n][D];
    printf("最大的收益为%d\n",w);
    for(i=1;i<=n;i++)
        printf("第%d号柜放%d个\n",i,x[i]);

}

四、运行结果