leetcode

0 class Solution {

1 static bool finished(const vector<int> needs) {

2 for (const int n : needs)

3 if (n) return false;

4 return true;

5 }

6

7 public:

8 int shoppingOffers(const vector<int> &price, const vector<vector<int>> &special, const vector<int> &needs,

9 int offer = 0, int cost = 0) const {

10 if (finished(needs)) return cost;

11

12 const int n = size(price);

13

14 int res = cost;

15 for (int i = 0; i < n; i++) {

16 res += needs[i] * price[i];

17 }

18

19 for (int i = offer; i < size(special); i++) {

20 int times = INT_MAX;

21 for (int j = 0; j < n && times; j++) {

22 if (!special[i][j]) continue;

23 times = min(times, needs[j] / special[i][j]);

24 }

25

26 if (!times) continue;

27

28 vector<int> next = needs;

29 int added = 0;

30

31 for (int k = 1; k <= times; k++) {

32 added += special[i].back();

33 if (cost + added >= res) break;

34 for (int j = 0; j < n; j++)

35 next[j] -= special[i][j];

36 res = min(res, shoppingOffers(price, special, next, i + 1, cost + added));

37 }

38 }

39

40 return res;

41 }

42 };