Ưu đãi mua sắm bằng C ++

Giả sử có một cửa hàng, có một số mặt hàng cần bán. Mỗi mặt hàng có một số giá. Tuy nhiên, có một số ưu đãi đặc biệt và ưu đãi đặc biệt bao gồm một hoặc nhiều loại mặt hàng khác nhau với giá ưu đãi. Vì vậy, chúng tôi có danh sách giá, một tập hợp các ưu đãi đặc biệt và số lượng chúng tôi cần mua cho mỗi mặt hàng. Nhiệm vụ là tìm ra mức giá thấp nhất mà chúng tôi phải trả cho chính xác một số mặt hàng nhất định như đã cho, nơi chúng tôi có thể sử dụng tối ưu các ưu đãi đặc biệt.

Ở đây, mỗi ưu đãi đặc biệt được thể hiện dưới dạng một mảng, số cuối cùng đại diện cho giá chúng ta cần trả cho ưu đãi đặc biệt này, các số khác đại diện cho số lượng mặt hàng cụ thể mà chúng ta có thể nhận được nếu mua ưu đãi này.

Vì vậy, nếu đầu vào là [2,5], [[3,0,5], [1,2,10]] và [3,2], thì đầu ra sẽ là 14. Điều này là do có hai loại của các mặt hàng, A và B. Giá của chúng lần lượt là $ 2 và $ 5. Trong ưu đãi đặc biệt 1, chúng tôi có thể trả $ 5 cho 3A và 0B. Trong ưu đãi đặc biệt 2, chúng tôi có thể trả $ 10 cho 1A và 2B. Chúng tôi cần mua 3A và 2B, vì vậy chúng tôi có thể trả 10 đô la cho 1A và 2B (ưu đãi đặc biệt 2) và 4 đô la cho 2A.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một bản đồ được gọi là bản ghi nhớ
Xác định một phương thức được gọi là directPurchase (), phương thức này có giá và cần các mảng
ret:=0
cho tôi trong phạm vi từ 0 đến kích thước của mảng giá - 1
- ret:=ret + giá [i] * cần [i]
trả lại ret
Xác định một phương pháp trợ giúp. Thao tác này sẽ lấy mảng giá, ma trận ưu đãi đặc biệt, nhu cầu mảng và chỉ số -
nếu bản ghi nhớ có nhu cầu thì hãy trả lại bản ghi nhớ [nhu cầu]
ret:=directPurchase (giá, nhu cầu)
cho tôi trong chỉ mục phạm vi đến số hàng của ma trận ưu đãi đặc biệt - 1
- nếu cần [j]
- chèn cần [j] - đặc biệt [i, j] vào mảng tạm thời
nếu đúng là đúng thì
- op1:=phần tử cột cuối cùng của trình trợ giúp [i] + đặc biệt (giá, đặc biệt, tạm thời, i)
- ret:=tối thiểu ret và op1
memo [nhu cầu]:=ret and return
Từ phương thức chính, thực hiện như sau -
người trợ giúp trả lại (giá, đặc biệt, nhu cầu, 0)

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Ưu đãi mua sắm bằng C ++

Ví dụ (C ++)

Đầu vào

Đầu ra