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

มีร้านขายสินค้าหลายชนิด แต่ละชนิดมีราคาปกติ มีข้อเสนอพิเศษ (special offers) แต่ละอันเป็นอาร์เรย์: ตัวสุดท้าย = ราคา ตัวอื่นๆ = จำนวนสินค้าแต่ละชนิดที่ได้ ต้องการซื้อสินค้าตาม needs ให้ราคาต่ำสุด

ตัวอย่าง: ราคา [2,5], โปรโมชัน [[3,0,5],[1,2,10]], ต้องการ [3,2] → คำตอบ 14 (ซื้อโปรโมชันที่ 2 ราคา 10 ได้ 1A+2B + ซื้อ A อีก 2 ชิ้น ราคา 4)

ขั้นตอนการแก้ปัญหา (DFS + Memoization)

1. ฟังก์ชัน directPurchase(price, needs) คำนวณราคาซื้อแยกต่างหาก
2. ฟังก์ชัน helper(price, special, needs, idx):
   • ถ้า อยู่ใน memo → คืนทันที
   • ret = directPurchase(price, needs)
   • ลองโปรโมชันแต่ละอันตั้งแต่ idx:
     • ถ้า needs[j] >= special[i][j] สำหรับทุก j → สร้าง temp = needs - special[i]
     • ret = min(ret, special[i].back() + helper(price, special, temp, i))
   • บันทึก memo และคืน ret
3. เริ่มจาก 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].back() + 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;
    }
};

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

Input

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

Output

14