C ++的购物优惠

假设有一家商店，有一些物品要卖。每个项目都有一些价格。但是，有一些特价商品，并且特价商品由一种或多种不同价格的商品组成。因此，我们提供了价格列表，一组特价商品以及我们需要为每个商品购买的数量。我们的任务是找到我们必须为给定的某些特定物品支付的最低价格，以便我们可以最佳地利用特价商品。

在这里，每个特价商品都以数组的形式表示，最后一个数字表示我们需要为此特价商品支付的价格，其他数字表示如果购买此特价商品可以得到多少个特定商品。

因此，如果输入像[2,5]，[[3,0,5]，[1,2,10]]和[3,2]，则输出将为14。这是因为有两种价格分别为2美元和5美元。在特价1中，我们可以为3A和0B支付5美元。在特价2中，我们可以为1A和2B支付10美元。我们需要购买3A和2B，因此我们可能要为10A和1B（特价2）支付10美元，为2A支付4美元。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个称为备忘录的映射

• 定义一个名为的方法directPurchase()，该方法需要价格并需要数组

• ret：= 0

• 对于价格范围大小为0的i – 1

• ret：= ret +价格[i] *需求[i]

• 返回ret

• 定义一种辅助方法。这将需要价格数组，特价矩阵，数组需求和索引-

• 如果备忘录有需要，则返回备忘录[需要]

• ret：= directPurchase（价格，需要）

• 对于范围索引中的i到特价商品矩阵的行数– 1

• 如果需要[j] <special [i，j]，则将ok设置为：= false，然后从循环中退出

• 在临时数组中插入need [j] – special [i，j]

• 如果确定是正确的，那么

• op1：= special [i] + helper（价格，特殊，临时，特殊）的最后一列元素

• ret：= ret和op1的最小值

• 备忘录[需要]：=退出并返回

• 从主要方法中执行以下操作-

• 返回助手（价格，特殊，需求，0）

范例（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   map <vector <int> , int> memo;
   int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
      return helper(price, special, needs, 0);
   }
   int helper(vector <int>& price, vector < vector <int> >& special, vector <int>& needs, int idx){
      if(memo.count(needs)) return memo[needs];
      int ret = directPurchase(price, needs);
      for(int i = idx; i < special.size(); i++){
         vector <int> temp;
         bool ok = true;
         for(int j = 0; j < special[i].size() - 1; j++){
            if(needs[j] < special[i][j]) {
               ok = false;
               break;
            }
            temp.push_back(needs[j] - special[i][j]);
         }
         if(ok){
            int op1 = special[i][special[i].size() - 1] + helper(price, special, temp, i);
            ret = min(ret, op1);
         }
      }
      return memo[needs] = ret;
   }
   int directPurchase(vector <int>& price, vector <int>& needs){
      int ret = 0;
      for(int i = 0; i < price.size(); i++){
         ret += price[i] * needs[i];
      }
      return ret;
   }
};
main(){
   vector<int> v1 = {2,5};
   vector<vector<int>> v2 = {{3,0,5},{1,2,10}};
   vector<int> v3 = {3,2};
   Solution ob;
   cout << (ob.shoppingOffers(v1, v2, v3));
}

输入值

[2,5]
[[3,0,5],[1,2,10]]
[3,2]

输出结果

14