Ưu đãi mua sắm (Shopping Offers) trong C++

Mô tả bài toán

Có các mặt hàng với giá gốc. Có các ưu đãi đặc biệt (bundle) bao gồm số lượng các mặt hàng và giá ưu đãi. Cho nhu cầu mua needs cho mỗi mặt hàng. Tìm chi phí nhỏ nhất.

Ví dụ: Giá [2,5], ưu đãi [[3,0,5],[1,2,10]], nhu cầu [3,2] → 14 (mua 1 ưu đãi 2 + 2 mặt hàng A riêng).

Giải thuật DFS + Memoization (DP trên trạng thái needs)

1. Trạng thái = vector needs còn lại.
2. Giá cơ bản = mua riêng lẻ theo giá gốc.
3. Thử áp dụng mỗi ưu đãi (nếu đủ nguyên liệu): đệ quy với needs - offer + giá ưu đãi.
4. Lấy min của tất cả lựa chọn. Dùng map memo hóa trạng thái needs.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    map<vector<int>, int> memo;
    int directBuy(vector<int>& price, vector<int>& needs) {
        int cost = 0;
        for (int i = 0; i < price.size(); i++) cost += price[i] * needs[i];
        return cost;
    }
    int dfs(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, int idx) {
        if (memo.count(needs)) return memo[needs];
        int res = directBuy(price, needs);
        for (int i = idx; i < special.size(); i++) {
            vector<int> next = needs;
            bool ok = true;
            for (int j = 0; j < needs.size(); j++) {
                if (needs[j] < special[i][j]) { ok = false; break; }
                next[j] -= special[i][j];
            }
            if (ok) {
                int cost = special[i].back() + dfs(price, special, next, i);
                res = min(res, cost);
            }
        }
        return memo[needs] = res;
    }
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        return dfs(price, special, needs, 0);
    }
};

int main() {
    vector<int> price = {2,5};
    vector<vector<int>> special = {{3,0,5},{1,2,10}};
    vector<int> needs = {3,2};
    Solution ob;
    cout << ob.shoppingOffers(price, special, needs); // 14
    return 0;
}

Độ phức tạp

• Thời gian: O(|special| * S) với S = số trạng thái needs (tùy dữ liệu).
• Không gian: O(S) cho memo.