数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的购物优惠
假设有一家商店，有一些商品要出售。每个商品都有一个价格。但是，有一些特价商品，特价商品包含一种或多种不同种类的商品，并有一个促销价格。所以我们有价格列表、一组特价商品以及我们需要购买每种商品的数量。任务是找到我们必须为完全确定的商品支付的最低价格，其中我们可以最佳地利用特价商品。
这里每个特价商品都以数组的形式表示，最后一个数字表示我们为这个特价商品需要支付的价格，其他数字表示如果我们购买这个特价商品可以获得多少特定商品。
所以如果输入像 [2,5]，[[3,0,5], [1,2,10]] 和 [3,2]，那么输出将是 14。这是因为有两种商品，A 和 B。它们的价格分别为 2 美元和 5 美元。在特价商品 1 中，我们可以支付 5 美元购买 3 个 A 和 0 个 B。在特价商品 2 中，我们可以支付 10 美元购买 1 个 A 和 2 个 B。我们需要购买 3 个 A 和 2 个 B，所以我们可以支付 10 美元购买 1 个 A 和 2 个 B（特价商品 2），以及 4 美元购买 2 个 A。
为了解决这个问题，我们将遵循以下步骤：
定义一个名为 memo 的映射
定义一个名为 directPurchase() 的方法，它接受 price 和 needs 数组
ret := 0
对于 i 从 0 到 price 数组的大小 - 1
ret := ret + price[i] * needs[i]
返回 ret
定义一个辅助方法。这将接受 price 数组、特价商品矩阵、数组 needs 和索引：
如果 memo 包含 needs，则返回 memo[needs]
ret := directPurchase(price, need)
对于 i 从 index 到特价商品矩阵的行数 - 1
如果 needs[j] < special[i, j]，则设置 ok := false，并退出循环
将 need[j] - special[i, j] 插入到 temp 数组中
如果 ok 为真，则
op1 := special[i] 的最后一列元素 + helper(price, special, temp, i)
ret := ret 和 op1 的最小值
memo[needs] := ret 并返回
从主方法执行以下操作：
返回 helper(price, special, needs, 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
234 次查看
