算法：布料切割问题 C语言实现

问题描述：

布料分割问题主要完成根据任意长宽（W、H）布料和任意大小模板的布（wi、hi）求解最优利用率以及给出最优分割方案的函数。

其中布料在切割时只能一刀切到底，不能停止。

如图：

输入样例：5.0 6.0                    2.0 3.0

                  2                            2

                 1.0 4.0                    1.0 3.0

                 2.0 3.0                    2.0 3,0

输出：     0.9333333             1.0

思路：利用分治算法，切一刀后分成两份，再对这两份进行处理。

代码：

#include <stdio.h>
#include <stdlib.h>
float Max(float a,float b)
{
    if(a>b)
        return a;
    else
        return b;
}
float getMax(int n,float *w,float *h,float W,float H)
{
    int i;
    float a[n],k;
    for(i=1;i<=n;i++)
    {
        if(w[i]==W&&h[i]==H)
            a[i]=1.0;
        else if(w[i]>W||h[i]>H)
            a[i]=0.0;
        else if(w[i]==W&&h[i]<H)
        {
            a[i]=(getMax(n,w,h,W,H-h[i])*W*(H-h[i])+getMax(n,w,h,W,h[i])*W*h[i])/(W*H);
        }
        else if(w[i]<W&&h[i]==H)
        {
            a[i]=(getMax(n,w,h,W-w[i],H)*H*(W-w[i])+getMax(n,w,h,w[i],H)*H*w[i])/(W*H);
        }
        else
        {
            a[i]=Max(((getMax(n,w,h,W-w[i],H)*(W-w[i])*H+getMax(n,w,h,w[i],H)*w[i]*H)/(W*H)),((getMax(n,w,h,W,H-h[i])*(H-h[i])*W+getMax(n,w,h,W,h[i])*W*h[i])/(W*H)));
        }
    }
    k=a[1];
    for(i=1;i<=n;i++)
    {
        if(a[i]>k)
        {
            k=a[i];
        }
    }
    return k;
}

int main()
{
    float W,H;
    int i;
    scanf("%f%f",&W,&H);
    int n;
    scanf("%d",&n);
    float w[n],h[n];
    for(i=1;i<=n;i++)
    {
        scanf("%f%f",&w[i],&h[i]);
    }
    printf("%f",getMax(n,w,h,W,H));
    return 0;
}

测试数据：