ข้อเสนอการช้อปปิ้งใน C++

สมมติว่ามีร้านค้า มีสินค้าบางอย่างที่จะขาย แต่ละรายการมีราคาบางส่วน อย่างไรก็ตาม มีข้อเสนอพิเศษบางอย่าง และข้อเสนอพิเศษประกอบด้วยสินค้าประเภทต่าง ๆ หนึ่งชนิดขึ้นไปที่มีราคาลด เราจึงมีรายการราคา ชุดข้อเสนอพิเศษ และจำนวนที่เราต้องซื้อสำหรับแต่ละรายการ งานคือการหาราคาต่ำสุดที่เราต้องจ่ายสำหรับสินค้าบางรายการตามที่กำหนด ซึ่งเราสามารถใช้ประโยชน์จากข้อเสนอพิเศษได้อย่างเหมาะสมที่สุด

ในที่นี้ข้อเสนอพิเศษแต่ละรายการจะแสดงในรูปแบบของอาร์เรย์ ตัวเลขสุดท้ายคือราคาที่เราต้องจ่ายสำหรับข้อเสนอพิเศษนี้ ตัวเลขอื่นๆ แสดงถึงจำนวนรายการเฉพาะที่เราจะได้รับหากเราซื้อข้อเสนอพิเศษนี้

ดังนั้นหากอินพุตเป็น [2,5], [[3,0,5], [1,2,10]] และ [3,2] ผลลัพธ์จะเป็น 14 เนื่องจากมีสองประเภท ของสินค้า A และ B ราคาอยู่ที่ $2 และ $5 ตามลำดับ ในข้อเสนอพิเศษ 1 เราสามารถจ่าย $5 สำหรับ 3A และ 0B ในข้อเสนอพิเศษ 2 เราสามารถจ่าย $10 สำหรับ 1A และ 2B เราจำเป็นต้องซื้อ 3A และ 2B ดังนั้นเราอาจจ่าย $10 สำหรับ 1A และ 2B (ข้อเสนอพิเศษ 2) ​​และ $4 สำหรับ 2A

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดแผนที่ที่เรียกว่าบันทึก

• กำหนดวิธีการที่เรียกว่า directPurchase() ซึ่งใช้ราคาและต้องการอาร์เรย์

• ยกเลิก :=0

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของอาร์เรย์ราคา – 1

  • ret :=ret + ราคา[i] * ต้องการ[i]

• รีเทิร์น

• กำหนดวิธีการช่วยเหลือหนึ่งวิธี สิ่งนี้จะใช้อาร์เรย์ราคา เมทริกซ์ข้อเสนอพิเศษ ความต้องการอาร์เรย์ และดัชนี -

• หากบันทึกมีความต้องการ ให้ส่งคืนบันทึก[ต้องการ]

• ret :=directPurchase(ราคา ต้องการ)

• สำหรับฉันอยู่ในช่วงดัชนีจำนวนแถวของเมทริกซ์ข้อเสนอพิเศษ – 1

  • ถ้าต้องการ[j] <พิเศษ[i, j] ให้ตั้งค่า ok :=false และออกจากลูป

  • ใส่ need[j] – พิเศษ[i, j] ลงใน temp array

• ถ้าตกลงเป็นจริงแล้ว

  • op1 :=องค์ประกอบคอลัมน์สุดท้ายของ special[i] + helper(price, special, temp, i)

  • ret :=ขั้นต่ำของ ret และ op1

• บันทึก[needs] :=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]

ผลลัพธ์

14