求教一个算法的题！解决办法

求教一个算法的题！
1、求解钢材切割的最佳订单。（60分）
（1）描述：编写程序，从订单中选择一组订单对钢材作切割加工，使钢材得到最佳利用，约定每一次切割会损耗固定长度的钢材（约定该值为2）。已知线型钢材总长度、订单数和各订单需要的钢材长度；
（2）输入：钢材总长度s、订单数n、各定单需要的钢材长度；
（3）输出：可以使钢材得到最佳利用的订单号、该订单需要的钢材长度。
例如：
Please input total length of the steel s： 28（回车）
Please input number of order n： 8（回车）
Please input the orders ：
5（回车）
6（回车）
7（回车）
8（回车）
9（回车）
10（回车）
12（回车）
15（回车）
屏幕输出:
Choice one order 1 length=5 order 3 length=7 order 7 length=12
Choice two order 2 length=6 order 4 length=8 order 6 length=10

------解决方案--------------------
人的知识比智商更重要，做算法题之前最重要的就是先学算法，如果你能凭智商想出高效算法，你就是迪杰斯特拉和高德纳，也不用学习了

I/O麻烦就不错了，搞个静态输出的，第一行输出分段长度，第二行输出有效总长度（去掉损耗的）

C/C++ code


static int **Pmax = NULL;
static int **Ptab = NULL;

void KnapsackPrint(const int *V, int row, int col)
{
    int e = 0;
    if (row > 0 && col > 0)
    {
        e = Ptab[row][col];
        if (e < 0)
        {
            if (row > 0 && col > 0)
                KnapsackPrint(V, row - 1, col + e);
            printf("%d ", V[row-1]);
        }
        else if (e > 0)
        {
            if (row > 0)
                KnapsackPrint(V, row - 1, col);
        }
    }
}

int KnapsackSteel(const int *V, const int *P, int n, int Vmax)
{
    int i = 0, j = 0;
    if (!V || !P || n <= 0 || Vmax <= 0)
        return 0;
    Pmax = (int**)malloc((n+1)*sizeof(int*));
    Ptab = (int**)malloc((n+1)*sizeof(int*));
    if (!Pmax || !Ptab)
        exit(-1);
    for (i=0; i<=n; ++i)
    {
        Pmax[i] = (int*)malloc((Vmax+1)*sizeof(int));
        Ptab[i] = (int*)malloc((Vmax+1)*sizeof(int));
        if (!Pmax[i] || !Ptab[i])
            exit(-1);
        memset(Pmax[i], 0x00, (Vmax+1)*sizeof(int));
        memset(Ptab[i], 0x00, (Vmax+1)*sizeof(int));
    }

    for (i=1; i<=n; ++i)
    {
        for (j=0; j<=Vmax; ++j)
        {
            if (i == 0 || j == 0)
            {
                Pmax[i][j] = 0;
            }
            else if (j < V[i-1] + 2)
            {
                Pmax[i][j] = Pmax[i-1][j];
                Ptab[i][j] = 1;
            }
            else
            {
                if (Pmax[i-1][j] > Pmax[i-1][j - V[i-1] - 2] + P[i-1])
                {
                    Pmax[i][j] = Pmax[i-1][j];
                    Ptab[i][j] = 1;
                }
                else
                {
                    Pmax[i][j] = Pmax[i-1][j - V[i-1] - 2] + P[i-1];
                    Ptab[i][j] = 0 - (V[i-1] + 2);
                }
            }
        }
    }

    KnapsackPrint(V, n, Vmax);
    printf("\n");

    return Pmax[n][Vmax];
}

int main()
{
    const int V[] = {5, 6, 7, 8, 9, 10, 12, 15};
    const int P[] = {5, 6, 7, 8, 9, 10, 12, 15};
    printf("%d\n", KnapsackSteel(V, P, sizeof(V)/sizeof(V[0]), 21));
    getchar();
}

求教一个算法的题！解决办法

相关推荐