LeetCode //C - 638. Shopping Offers
638. Shopping OffersIn LeetCode Store, there are n items to sell. Each item has a price. However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.
You are given an integer array price where price is the price of the i t h i^{th} ith item, and an integer array needs where needs is the number of pieces of the i t h i^{th} ith item you want to buy.
You are also given an array special where special is of size n + 1 where special is the number of pieces of the j t h j^{th} jth item in the i t h i^{th} ith offer and special (i.e., the last integer in the array) is the price of the i t h i^{th} ith offer.
Return the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers. You are not allowed to buy more items than you want, even if that would lower the overall price. You could use any of the special offers as many times as you want.
Example 1:
Input: price = , special = [,], needs =
Output: 14
Explanation: There are two kinds of items, A and B. Their prices are $2 and $5 respectively.
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B.
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.
Example 2:
Input: price = , special = [,], needs =
Output: 11
Explanation: The price of A is $2, and $3 for B, $4 for C.
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C.
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C.
You cannot add more items, though only $9 for 2A ,2B and 1C.
Constraints:
[*]n == price.length == needs.length
[*]1 <= n <= 6
[*]0 <= price, needs <= 10
[*]1 <= special.length <= 100
[*]special.length == n + 1
[*]0 <= special <= 50
[*]The input is generated that at least one of special is non-zero for 0 <= j <= n - 1.
From: LeetCode
Link: 638. Shopping Offers
Solution:
Ideas:
- Recursive Approach with Memoization
- Uses recursion to explore all possible ways to buy items, considering both normal prices and special offers.
- Stores previously computed results in a hash-based memoization table to avoid redundant calculations.
- Base Case
- If no special offer can be applied, the cost is simply needs * price for each item.
- Processing Special Offers
- Checks if a special offer is valid (i.e., does not exceed the required quantity).
- Recursively computes the minimum cost after applying the offer.
- Updates the minimum cost accordingly.
- Memoization Optimization
- Stores computed results to avoid recomputation.
- Uses hashing to efficiently track different needs states.
- Function Renaming Fix
- Renamed minCost to computeMinCost to avoid naming conflicts.
Code:
#define MAX_N 6
#define HASH_SIZE 10007
typedef struct {
int key;
int cost;
} MemoEntry;
MemoEntry memo;
int memoSize = 0;
int hashKey(int *needs, int needsSize) {
int hash = 0;
for (int i = 0; i < needsSize; i++) {
hash = hash * 31 + needs;
}
return hash % HASH_SIZE;
}
int findInMemo(int *needs, int needsSize) {
for (int i = 0; i < memoSize; i++) {
if (memcmp(memo.key, needs, needsSize * sizeof(int)) == 0) {
return memo.cost;
}
}
return -1;
}
void storeInMemo(int *needs, int needsSize, int cost) {
memcpy(memo.key, needs, needsSize * sizeof(int));
memo.cost = cost;
memoSize++;
}
int computeMinCost(int* price, int priceSize, int** special, int specialSize, int* needs, int needsSize) {
int stored = findInMemo(needs, needsSize);
if (stored != -1) return stored;
// Compute cost without special offers
int normalCost = 0;
for (int i = 0; i < needsSize; i++) {
normalCost += needs * price;
}
int minTotalCost = normalCost;// Store the current minimum cost
// Try each special offer
for (int i = 0; i < specialSize; i++) {
int newNeeds;
int valid = 1;
for (int j = 0; j < needsSize; j++) {
if (special > needs) {
valid = 0;
break;
}
newNeeds = needs - special;
}
if (valid) {
int offerCost = special + computeMinCost(price, priceSize, special, specialSize, newNeeds, needsSize);
if (offerCost < minTotalCost) {
minTotalCost = offerCost;
}
}
}
storeInMemo(needs, needsSize, minTotalCost);
return minTotalCost;
}
int shoppingOffers(int* price, int priceSize, int** special, int specialSize, int* specialColSize, int* needs, int needsSize) {
memoSize = 0;
return computeMinCost(price, priceSize, special, specialSize, needs, needsSize);
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]