C++でのショッピングオファー

店舗があるとすると、販売するアイテムがいくつかあります。各アイテムにはいくつかの価格があります。ただし、いくつかの特別オファーがあり、特別オファーは、セール価格の1つまたは複数の異なる種類のアイテムで構成されます。つまり、価格のリスト、一連の特別オファー、および各アイテムに対して購入する必要のある数があります。タスクは、特別オファーを最適に利用できる、与えられた特定のアイテムに支払う必要のある最低価格を見つけることです。

ここで、各特別オファーは配列の形式で表され、最後の数字はこの特別オファーに支払う必要のある価格を表し、他の数字はこのオファーを購入した場合に取得できる特定のアイテムの数を表します。

したがって、入力が[2,5]、[[3,0,5]、[1,2,10]]、[3,2]の場合、出力は14になります。これは2種類あるためです。アイテムのAとB。それらの価格はそれぞれ2ドルと5ドルです。特別オファー1では、3Aと0Bに5ドルを支払うことができます。特別オファー2では、1Aと2Bに$10を支払うことができます。 3Aと2Bを購入する必要があるため、1Aと2B（特別オファー2）に10ドル、2Aに4ドル支払う場合があります。

これを解決するには、次の手順に従います-

• メモと呼ばれるマップを定義する

• directPurchase（）というメソッドを定義します。これには価格がかかり、配列が必要です

• ret：=0

• 0から価格配列のサイズまでの範囲のiの場合– 1

  • ret：=ret + price [i] * need [i]

• retを返す

• 1つのヘルパーメソッドを定義します。これには、価格配列、特別オファーマトリックス、配列のニーズ、およびインデックスが必要です-

• メモにニーズがある場合は、メモを返します[必要]

• ret：=directPurchase（price、need）

• 特別オファーマトリックスの行数に対する範囲インデックスのiの場合– 1

  • 必要な場合[j]

  • need [j] – special [i、j]を一時配列に挿入

• okがtrueの場合、

  • op1：=special [i] + helper（price、special、temp、i）の最後の列要素

  • ret：=retとop1の最小値

• memo [needs]：=ret and return

• メインの方法から、次のようにします-

• リターンヘルパー（価格、特別、ニーズ、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