資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
