[数据结构与算法]数据结构与算法-最少费用购物

• 题目：商店中每种商品都有标价。例如，一朵花的价格是 2 元，一个花瓶的价格是 5 元。为了 吸引顾客，商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组，并降价销 售。例如，3 朵花的价格不是 6 元而是 5 元，2 个花瓶加 1 朵花的优惠价是 10 元。试设计一 算法，计算出某一顾客所购商品应付的最少费用。
• 数据输入：提供欲购商品数据。第 1 行中有 1 个整数 B（0≤B≤5），表示所购商品种类数。接下来的 B 行，每行有 3 个数 C，K 和 P。C 表示商品的编码（每种商品有唯一编码），1≤C≤999。 K 表示购买该种商品总数，1≤K≤5。P是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，一次最多购买 5x5=25 件商品。
  提供优惠商品价数据。第 1 行中有 1 个整数 S（0≤S≤99），表示共有 S 种优惠商品组合。接下来的 S 行，每行的第 1 个数描述优惠商品组合中商品的种类数 j。接着是 j 个数字对（C，K），其中 C 是商品编码，1≤C≤999。K 表示该种商品在此组合中的数量，1≤K≤5。每行最后 1 个数字 P（1≤P≤9999）表示此商品组合的优惠价。
• 数据输出：输出计算出的所购商品应付的最少费用。
• 样例：
  输入： 2 2
  7 3 2 1 7 3 5
  8 2 5 2 7 1 8 2 10
  输出： 14
• 代码

  /**
   * 最少费用购物
   */
  #include <iostream>
  #include <iomanip>
  #include <algorithm>  //sort
  #include <map>
  #include <queue>
  #include <deque>  //双端队列，头可插，尾可插
  #include <string>
  #include <stack>
  #include <ctime>
  #include <climits> //数值的限制范围
  //(double)clock() / CLOCKS_PER_SEC <= 0.95 限制0.95s跑完
  using namespace std;
  
  class Player {
  private:
      //通用属性
      static const int MAX = int(1e7);
      static const long long INF = (long long)1e18;
  private:
      //个例属性
      int n, m;
  
      struct _Item {
          int id; //原始id
          int need;
          int price;
      } Item[10]{};
      int ID[10000]{}; //离散化后的id
  
      struct _Offer {
          int sum;
          int num[10]; //下标就是离散化后的id
          int price;
      } Offer[100]{};
  
      int num[10][10][10][10][10]{};
    
  private:
      //个例方法
      void dp() {
  
      }
  
  private:
      //通用方法
      void BeginPlay() {
          cin >> n;
          for (int i = 1; i <= n; ++i) {
              cin >> Item[i].id
                  >> Item[i].need
                  >> Item[i].price;
              ID[Item[i].id] = i; //离散化
          }
          cin >> m;
          for (int i = 1; i <= m; ++i) {
              cin >> Offer[i].sum;
              int id;
              for (int j = 1; j <= Offer[i].sum; ++j) {
                  cin >> id;
                  id = ID[id]; //得到商品离散化后的id
                  cin >> Offer[i].num[id];
              }
              cin >> Offer[i].price;
          }
      }
  
      void Playing() {
        	//从0开始是因为商品可以买0件
          for (int i = 0; i <= Item[1].need; ++i) {
              for (int j = 0; j <= Item[2].need; ++j) {
                  for (int k = 0; k <= Item[3].need; ++k) {
                      for (int l = 0; l <= Item[4].need; ++l) {
                          for (int p = 0; p <= Item[5].need; ++p) {
                              int Min = i * Item[1].price +
                                  j * Item[2].price +
                                  k * Item[3].price +
                                  l * Item[4].price +
                                  p * Item[5].price;
                              for (int s = 1; s <= m; ++s) {
                                  int newI = i - Offer[s].num[ID[Item[1].id]];
                                  int newJ = j - Offer[s].num[ID[Item[2].id]];
                                  int newK = k - Offer[s].num[ID[Item[3].id]];
                                  int newL = l - Offer[s].num[ID[Item[4].id]];
                                  int newP = p - Offer[s].num[ID[Item[5].id]];
                                  if (newI < 0 || newJ < 0 || newK < 0 || newL < 0 || newP < 0) {
                                      continue;
                                  }
                                  else {
                                      Min = min(Min,num[newI][newJ][newK][newL][newP] + Offer[s].price);
                                  }
                              }
                              num[i][j][k][l][p] =Min;
                          }
                      }
                  }
              }
          }
      }
  
      void EndPlay() {
          cout << num[Item[1].need]
              [Item[2].need]
              [Item[3].need]
              [Item[4].need]
              [Item[5].need];
      }
  
  public:
      //通用方法
      void Play() {
          BeginPlay();
          Playing();
          EndPlay();
      }
  };
  
  Player Moota;
  
  int main() {
  
      Moota.Play();
  }