最少费用购物
?问题描述：
商店中每种商品都有标价。例如，一朵花的价格是2元。一个花瓶的价格是5 元。为了
吸引顾客，商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组，并降价销
售。例如，3朵花的价格不是6元而是5元。2 个花瓶加1 朵花的优惠价是10 元。试设计一 个算法，计算出某一顾客所购商品应付的最少费用。
编程任务：
对于给定欲购商品的价格和数量，以及优惠商品价，编程计算所购商品应付的最少费用。
Input
由文件input.txt提供欲购商品数据。文件的第1行中有1 个整数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提供优惠商品价数据。文件的第1行中有1 个整数S（0≤S≤99），表示
共有S 种优惠商品组合。接下来的S 行，每行的第一个数描述优惠商品组合中商品的种类数 j。接着是j 个数字对（C，K），其中C 是商品编码，1≤C≤999。K 表示该种商品在此组合 中的数量，1≤K≤5。每行最后一个数字P（1≤ P≤9999）表示此商品组合的优惠价。
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的最小费用。：
F（A1，A2，A3，A4，A5） （1）
考虑这个状态的由来，当然，我们不用优惠商品也可以买，显然这样不是最优。于是如果我们能够使用第I条商品组合的话，状态就便为了：
F（A1-SI1，A2-SI2，A3-SI3，A4-SI4，A5-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;
}