C++의 쇼핑 제안

<시간/>

상점이 있고 판매할 품목이 있다고 가정합니다. 각 항목에는 약간의 가격이 있습니다. 그러나 몇 가지 특별 제안이 있으며 특별 제안은 할인 가격의 하나 이상의 다른 종류의 품목으로 구성됩니다. 따라서 가격 목록, 특별 제안 세트 및 각 품목에 대해 구매해야 하는 번호가 있습니다. 임무는 주어진 대로 정확히 특정 품목에 대해 지불해야 하는 최저 가격을 찾는 것입니다. 여기서 특별 제안을 최적으로 사용할 수 있습니다.

여기에서 각 특별 제안은 배열 형태로 표시되며, 마지막 숫자는 이 특별 제안에 대해 지불해야 하는 가격을 나타내고, 다른 숫자는 이 제안을 구매할 경우 얻을 수 있는 특정 항목의 수를 나타냅니다.

따라서 입력이 [2,5], [[3,0,5], [1,2,10]] 및 [3,2]와 같으면 출력은 14가 됩니다. 두 가지 종류가 있기 때문입니다. 품목 A 및 B. 가격은 각각 $2 및 $5입니다. 특별 제안 1에서 3A 및 0B에 대해 5달러를 지불할 수 있습니다. 특별 제안 2에서는 1A 및 2B에 대해 10달러를 지불할 수 있습니다. 3A와 2B를 구매해야 하므로 1A와 2B(특별 제안 2)에 10달러, 2A에 4달러를 지불할 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

메모라는 지도 정의
directPurchase()라는 메서드를 정의합니다. 이 메서드는 가격과 배열이 필요합니다.
ret :=0
범위 0에서 가격 배열의 크기 – 1까지의 i에 대해
- ret :=ret + price[i] * 필요[i]
리턴 렛
하나의 도우미 메서드를 정의합니다. 여기에는 가격 배열, 특별 제안 매트릭스, 배열 요구 사항 및 인덱스가 필요합니다. -
메모에 필요한 사항이 있으면 메모[needs]를 반환합니다.
ret :=directPurchase(가격, 필요)
특별 제안 행렬의 행 수에 대한 범위 인덱스의 i에 대해 - 1
- if need[j]
- 필요[j] 삽입 – 특수[i, j]를 임시 배열에 삽입
ok가 참이면
- op1 :=special[i]의 마지막 열 요소 + helper(price, special, temp, i)
- ret :=ret 및 op1의 최소값
메모[필요] :=ret 및 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]