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