Practice/Uber/Leetcode 638. Shopping Offers

Leetcode 638. Shopping Offers

CodingOptional

Problem

You are shopping for multiple items, and the store provides both regular unit prices and special bundle offers. Your task is to find the minimum cost to purchase exactly the quantities you need.

You are given:

• An array prices where prices[i] is the unit price of item i

• An array offers where each offers[j] is a special bundle containing:

  • The first n elements represent quantities of each item in the bundle
  • The last element is the price of the entire bundle

• An array needs where needs[i] is the exact quantity of item i you must purchase

Special offers can be used multiple times, but you cannot purchase more of any item than required. Return the minimum total cost to buy exactly the quantities specified in needs.

Requirements

1. Calculate the minimum cost to purchase exactly the required quantities
2. You may use each special offer zero or more times
3. You cannot exceed the required quantity for any item
4. If no offers save money, buying at unit prices may be optimal
5. Return the minimum total cost as an integer

Constraints

• 1 <= prices.length <= 6
• 0 <= offers.length <= 100
• 1 <= prices[i], needs[i] <= 10
• Each offer has length prices.length + 1
• 0 <= offers[j][k] <= 10 for item quantities
• 1 <= offers[j][prices.length] <= 100 for offer price

Examples

Example 1:

Input: prices = [2, 5], offers = [[3, 0, 5], [1, 2, 10]], needs = [3, 2] Output: 14 Explanation: Use the second offer [1, 2, 10] once to get 1 of item 0 and 2 of item 1 for \$10. Then buy the remaining 2 units of item 0 at unit price \$2 each. Total cost: 10 + 2 + 2 = 14 dollars.

Example 2:

Input: prices = [2, 3, 4], offers = [[1, 1, 0, 12]], needs = [1, 2, 1] Output: 11 Explanation: The offer costs \$12 for 1 of item 0 and 1 of item 1, but buying individually costs 2 + 3 = 5 for those items. It's cheaper to buy all items at unit prices: 2*1 + 3*2 + 4*1 = 11 dollars.

Example 3:

Input: prices = [2, 3], offers = [[1, 1, 3]], needs = [3, 3] Output: 9 Explanation: The offer provides 1 of each item for \$3. Use it three times to get exactly 3 of each item. Total cost: 3 * 3 = 9 dollars.