最少费用购物 动态规划

2013年10月31日 9点热度 0条评论 来源: fool宋

最少费用购物

?问题描述: 

商店中每种商品都有标价。例如,一朵花的价格是2元。一个花瓶的价格是元。为了 

吸引顾客,商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组,并降价销 

售。例如,3朵花的价格不是6元而是5元。个花瓶加朵花的优惠价是10 元。试设计一 个算法,计算出某一顾客所购商品应付的最少费用。 

编程任务: 

对于给定欲购商品的价格和数量,以及优惠商品价,编程计算所购商品应付的最少费用。

Input 

由文件input.txt提供欲购商品数据。文件的第1行中有个整数B0B5),表示所 

购商品种类数。接下来的行,每行有个数CP表示商品的编码(每种商品有 唯一编码),1C999表示购买该种商品总数,1K5是该种商品的正常单价(每 件商品的价格),1P999。请注意,一次最多可购买5*525件商品。 

由文件offer.txt提供优惠商品价数据。文件的第1行中有个整数S0S99),表示 

共有种优惠商品组合。接下来的行,每行的第一个数描述优惠商品组合中商品的种类数 j。接着是个数字对(CK),其中是商品编码,1C999表示该种商品在此组合 中的数量,1K5。每行最后一个数字P1≤ P9999)表示此商品组合的优惠价。

 

Output 

 

程序运行结束时,将计算出的所购商品应付的最少费用输出到文件output.txt中。

 

Sample Input 

 

input.txt

 

2

 

7 3 2

 

8 2 5

 

offer.txt

 

2

 

1 7 3 5

 

2 7 1 8 2 10

 

Sample Output 

 

14

一、问题描述

   某商店中每种商品都有一个价格。例如,一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位);一个花瓶的价格是5 ICU。为了吸引更多的顾客,商店提供了特殊优惠价。

    特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不是6而是5 ICU ;2个花瓶加1朵花是10 ICU不是12 ICU。

    编一个程序,计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意,你不能变更顾客所购商品的种类及数量,即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述,并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14 ICU因为:

         1朵花加2个花瓶: 优惠价:10  ICU

         2朵花            正常价: 4  ICU

输入数据

    用两个文件表示输入数据。第一个文件INPUT.TXT描述顾客所购物品(放在购物筐中);第二个文件描述商店提供的优惠商品及价格(文件名为OFFER.TXT)。 两个文件中都只用整数。

    第一个文件INPUT.TXT的格式为:第一行是一个数字B(0≤B≤5),表示所购商品种类数。下面共B行,每行中含3个数C,K,P。C 代表商品的编码(每种商品有一个唯一的编码),1≤C≤999。K代表该种商品购买总数,1≤K≤5。P 是该种商品的正常单价(每件商品的价格),1≤P≤999。请注意,购物筐中最多可放5*5=25件商品。

第二个文件OFFER.TXT的格式为:第一行是一个数字S(0≤S≤99),表示共有S种优惠。下面共S行,每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对(C,K),其中C代表商品编码,1≤C≤9 99。K代表该种商品在此组合中的数量,1≤K≤5。本行最后一个数字P(1≤P≤9999)代表此商品组合的优惠价。当然, 优惠价要低于该组合中商品正常价之总和。

 

输出数据

在输出文件OUTPUT.TXT中写 一个数字(占一行), 该数字表示顾客所购商品(输入文件指明所购商品)应付的最低货款。

二、分析

       初看这道题目,我的感觉是似曾相识,同我们做的背包问题差不多。只是背包问题是给定容量,求最大价值的东西。而这道题目是给定所放的东西,求最小的费用(对应背包问题为最小的容量)。恰好是一个求最值的“逆问题”。背包问题是经典的动态规划问题,那么这道题呢?

由于动态规划要满足无后效性和最优化原理,所以我们来分析此题是否满足以上两点。先来状态表示的方法,商品不超过5种,而每种采购的数量又不超过5,那么用一个五元组来表示第I种商品买AI的最小费用。:

FA1A2A3A4A5                      1

考虑这个状态的由来,当然,我们不用优惠商品也可以买,显然这样不是最优。于是如果我们能够使用第I条商品组合的话,状态就便为了:

FA1-SI1A2-SI2A3-SI3A4-SI4A5-SI5 2

这样的话,状态1的费用为状态2的费用加上SI的费用,而状态2的费用必须最低(很显然,用反证法即可),同时,我们也不管状态2是如何来的(因为每一个优惠商品组合的使用是没有限制的),所以本题既满足无后效性,又符合最优化原理,同时还有大量重叠子问题产生,动态规划解决此题是最好不过了。

通过对问题的分析,我们知道了状态的表示和转移的基本方法,我们很容易得到一个状态转移方程:

F [a, b, c, d, e] = Min {F [a-S1, b-S2, c-S3, d-S4, e-S5] + SaleCost [S]}

初始条件为:

F [a, b, c, d, e] = Cost [1]*a+Cost [2]*b+Cost [3]*c+Cost [4]*d+Cost [5]*e

即不用优惠的购买费用。


#include<stdio.h>
#include<stdlib.h>
int main()
{
    int num[1000];//货品标号对应的第几种物品
    int I[5][3]={0};//购买的物品标号,个数,单价
    int O[99][12]={0};//优惠方案(种类,商品标号及个数,总价)
    int C,K,P,B,S;
    //C商品的编码
    //K购买该种商品的数量
    //P该种商品的正常单价
    //B所购商品种类数
    //S优惠商品组合数
    int i[5],j[5];
    int m,n,x,y,z;
    int min;
    int work[6][6][6][6][6];
    FILE *fp;
    fp=fopen("input0.txt","r");
    fscanf(fp,"%d",&B);
    for(m=0;m<B;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("OFFER0.TXT","r");
    fscanf(fp,"%d",&S);
    for(m=0;m<S;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<S;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)
									 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]]);
    return 0;
}

    原文作者:fool宋
    原文地址: https://blog.csdn.net/foolsong/article/details/13869493
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。