最少费用购物

Description

?问题描述：

商店中每种商品都有标价。例如，一朵花的价格是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

————————————————————

#include <iostream>
#include <map>
using namespace std;

const int N = 10;
const int M = 1005;
int cost[N][N][N][N][N];
struct node
{
   int c, k, p;
}product[N];
int p[N];
int offer[M][N];
int n, m;

void minicost()
{
   int a,b,c,d,e,pp, minm;
   minm = 0;
   for (int i=1; i <= n; i++)
       minm += p[i] * product[i].p;
   for (pp=1; pp<=m; pp++)
   {
       a = p[1] – offer[pp][1];
       b = p[2] – offer[pp][2];
       c = p[3] – offer[pp][3];
       d = p[4] – offer[pp][4];
       e = p[5] – offer[pp][5];
       if (a >=0 && b>=0 && c>=0 && d>=0 && e >=0 && cost[a][b][c][d][e]+offer[pp][0] < minm)
           minm = cost[a][b][c][d][e]+ offer[pp][0];
   }
   cost[p[1]][p[2]][p[3]][p[4]][p[5]] = minm;
}

void dfs(int i)
{
   if (i > n)
   {
       minicost ();
       return;
   }
   for (int j = 0; j <= product[i].k; j ++)
   {
       p[i] = j;
       dfs(i+1);
   }
}

void init()
{
   int a, b, c, d,e;
   for (a=0; a<N; a++)
       for (b = 0; b<N; b++)
           for (c = 0; c<N; c++)
               for (d = 0; d<N; d++)
                   for (e = 0; e<N; e++)
                       cost[a][b][c][d][e] = 0;
   memset(p, 0, sizeof(p));
   for (int i=0; i<=M; i++)
   {
       for (int j=0; j<=N; j++)
           offer[i][j] = 0;
       product[i].c=product[i].k= product[i].p = 0;
   }
}

int main()
{
   //freopen (“in.txt”, “r”,stdin);
   while (scanf (“%d”, &n) == 1)
   {
       map<int, int> M;
       M.clear();
       init();
       int i, j;
       for (i  = 1; i<=n; i++)
       {
           scanf (“%d%d%d”, &product[i].c, &product[i].k, &product[i].p);
           M[product[i].c]  = i;
       }
       scanf (“%d”, &m);
       for (i=1; i<=m; i++)
       {
           int nn;
           scanf (“%d”, &nn);
           for (j=0; j<nn; j++)
           {
               int c, k;
               scanf (“%d%d”, &c, &k);
               offer[i][M[c]] = k;
           }
           int k;
           scanf (“%d”, &k);
           offer[i][0] = k;
       }
       //memset(cost,INT_MAX, sizeof(cost));
       dfs(1);

       printf (“%d\n”, cost[product[1].k][product[2].k][product[3].k][product[4].k][product[5].k]);
   }
}