新手题一道
有一个由数字1，2，3，。。。9组成的数字串（长度不超过200），问如何将M（M<=20)个加号插入到这个数字串中，使得所形成算数表达式值最小？用回溯法思想做

[解决办法]

C/C++ code

#include "stdio.h"#include "stdlib.h"#include "string.h"typedef unsigned char BYTE;void AddPlus(BYTE * pList, long nCount,              long nStart, long nEnd,              long nAllLevel, long nCurrentLevel,             long * pPos, long * pBestPos, double & dMin);double CalcSum(BYTE * pList, long nCount, long * pPos);void PrintResult(BYTE * pList, long nCount, long * pPos, double dValue);void main(){    char strList[201];    BYTE pList[201];    long pPos[21];    long pBestPos[21];    long nAllLevel;    long nCount;    double dMin = 1;    printf("Please input number list:\n");    scanf("%s", strList);    printf("Please input count of (+): \n");    scanf("%d", &nAllLevel);        nCount = strlen(strList);    for (long k=0; k<nCount; k++)        dMin *= 10;    memset(pList, 0, nCount);    for (k=0; k<nCount; k++)    {        if (strList[k]>='0' && strList[k]<='9')            pList[k] = strList[k] - '0';    }    pPos[nAllLevel] = nCount-1;    AddPlus(pList, nCount, 0, nCount-1-nAllLevel, nAllLevel, 0, pPos, pBestPos, dMin);    printf("\nBest Solution:\n");    double dBest = CalcSum(pList, nCount, pBestPos);    PrintResult(pList, nCount, pBestPos, dBest);    getchar();    getchar();}void AddPlus(BYTE * pList, long nCount,              long nStart, long nEnd,              long nAllLevel, long nCurrentLevel,             long * pPos, long * pBestPos, double & dMin){    if (nCurrentLevel == nAllLevel)    {        double dValue = CalcSum(pList, nCount, pPos);        if (dValue < dMin)        {            dMin = dValue;            memcpy(pBestPos, pPos, (nAllLevel+1) * sizeof(long));        }        //        PrintResult(pList, nCount, pPos, dValue);        return;    }    for (long k=nStart; k<=nEnd; k++)    {        pPos[nCurrentLevel] = k;        AddPlus(pList, nCount,             k+1, nCount-nAllLevel+nCurrentLevel,             nAllLevel, nCurrentLevel+1,             pPos, pBestPos, dMin);    }}double CalcSum(BYTE * pList, long nCount, long * pPos){    double dSum=0;    double dCurrent=0;    long nLevel=0;    for (long k=0; k<nCount; k++)    {        dCurrent = dCurrent*10 + pList[k];        if (k == pPos[nLevel])        {            dSum += dCurrent;            dCurrent=0;            nLevel++;        }    }    return dSum;}void PrintResult(BYTE * pList, long nCount, long * pPos, double dValue){    double dSum=0;    double dCurrent=0;    long nLevel=0;    for (long k=0; k<nCount; k++)    {        printf("%d", pList[k]);        if (k == pPos[nLevel] && k!=nCount-1)        {            printf("+");            nLevel++;        }    }    if (dValue<1E8)        printf("=%d\n", (long)dValue);    else        printf("=%lf\n", dValue); }