最少费用购物问题完全解决方案

动态规划解决最少费用购物问题 算法设计与分析 王晓东 3.17课后答案

#include
#include
int main（）
{
    int num[1000];//货品标号对应的第几种物品
    int I[5][3]={0};//购买的物品标号，个数，单价
    int O[99][12]={0};//优惠方案（种类，商品标号及个数，总价）
    int CKPBS;
    //C商品的编码
    //K购买该种商品的数量
    //P该种商品的正常单价
    //B所购商品种类数
    //S优惠商品组合数
    int i[5]j[5];
    int mnxyz;
    int min;
    int work[6][6][6][6][6];
    FILE *fp;
    fp=fopen（“input10.txt““r“）;
    fscanf（fp“%d“&B）;
    for（m=0;m    {
        fscanf（fp“%d%d%d“&C&K&P）;
        I[m][0]=C;
        I[m][1]=K;
        I[m][2]=P;
        num[C]=m;
    } 
    fclose（fp）;
    fp=fopen（“OFFER10.TXT““r“）;
    fscanf（fp“%d“&S）;
    for（m=0;m    {
        fscanf（fp“%d“&y）;
        O[m][0]=y;
        for（n=1;n<=2*y;n++）
        {
            fscanf（fp“%d“&x）;
            if（n%2==1）
            {
                O[m][n]=num[x];
            }
            else
            O[m][n]=x;
        }
        fscanf（fp“%d“&O[m][n]）;
    }
    
    
    work[0][0][0][0][0]=0;
    
    for（i[0]=0;i[0]<=I[0][1];i[0]++）
    {
        for（i[1]=0;i[1]<=I[1][1];i[1]++）
        {
            for（i[2]=0;i[2]<=I[2][1];i[2]++）
            {
                for（i[3]=0;i[3]<=I[3][1];i[3]++）
                {
                    for（i[4]=0;i[4]<=I[4][1];i[4]++）
                    {
                        if（i[0]==0&&i[1]==0&&i[2]==0&&i[3]==0&&i[4]==0）
                        continue;
                        else
                        {
							work[i[0]][i[1]][i[2]][i[3]][i[4]]=1000000;
                            min=i[0]*I[0][2]+i[1]*I[1][2]+i[2]*I[2][2]+
                                i[3]*I[3][2]+i[4]*I[4][2];
                            for（m=0;m                            {
                                for（n=0;n<5;n++）
                                j[n]=i[n];
                                for（n=1;n<=2*O[m][0];n=n+2）
                                {
                                    if（i[O[m][n]]-O[m][n+1]<0）
                                    j[O[m][n]]=0;
                                    else 
                                    j[O[m][n]]=i[O[m][n]]-O[m][n+1];
                                }
                                if（work[j[0]][j[1]][j[2]][j[3]][j[4]]
                                   +O[m][n]                                min=work[j[0]][j[1]][j[2]][j[3]][j[4]]
                                    +O[m][n];
                            }
                            work[i[0]][i[1]][i[2]][i[3]][i[4]]=min;
                        }
                    }
                }
            }
        }
    }
    printf（“%d\n“work[I[0][1]][I[1][1]][I[2][1]][I[3][1]][I[4][1]]）;
    system（“pause“）;
    return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       2859  2009-09-19 14:40  3.17\3_17.cpp

     文件         17  2006-02-03 16:49  3.17\input0.txt

     文件          1  2006-02-03 09:25  3.17\input1.txt

     文件         48  2006-02-03 10:26  3.17\input2.txt

     文件         52  2006-02-03 10:27  3.17\input3.txt

     文件         41  2006-02-03 10:17  3.17\input4.txt

     文件         45  2006-02-03 11:03  3.17\input5.txt

     文件         30  2006-02-03 11:18  3.17\input6.txt

     文件         43  2006-02-03 11:26  3.17\input7.txt

     文件         53  2006-02-03 12:43  3.17\input8.txt

     文件         53  2006-02-03 12:58  3.17\input9.txt

     文件         54  2006-02-03 13:03  3.17\input10.txt

     文件         26  2006-02-03 16:49  3.17\OFFER0.TXT

     文件          1  2006-02-03 09:25  3.17\OFFER1.TXT

     文件          1  2006-02-03 09:27  3.17\OFFER2.TXT

     文件         57  2006-02-03 10:09  3.17\OFFER3.TXT

     文件         71  2006-02-03 10:17  3.17\OFFER4.TXT

     文件        170  2006-02-03 11:03  3.17\OFFER5.TXT

     文件        914  2006-02-03 11:18  3.17\OFFER6.TXT

     文件       1460  2006-02-03 11:26  3.17\OFFER7.TXT

     文件        913  2006-02-03 12:43  3.17\OFFER8.TXT

     文件       1543  2006-02-03 12:58  3.17\OFFER9.TXT

     文件       2029  2006-02-03 13:03  3.17\OFFER10.TXT

     文件      24770  2009-09-19 14:10  3.17\3_17.exe

     目录          0  2009-09-19 14:01  3.17

----------- ---------  ---------- -----  ----

                35251                    25