Minimum Cost to Achieve at Least a Given Weight
Problem Statement
You are given an integer array cost of length n, where cost[i] represents the cost of an item with weight 2^i.
The available item weights are powers of two: 1, 2, 4, 8, 16, ....
You can purchase any number of items of each available weight.
Given an integer minWeight, find the minimum total cost required to obtain a combined weight greater than or equal to minWeight.
The total weight is allowed to exceed minWeight, but it must never be less than the target.
Examples
Example 1
Input:
cost = [2, 5, 7, 11, 25]
minWeight = 26Output:
37Explanation:
The available items have the following weights and costs:
| Weight | Cost per item |
|---|---|
| 1 | 2 |
| 2 | 5 |
| 4 | 7 |
| 8 | 11 |
| 16 | 25 |
One optimal selection is two items of weight 1 and three items of weight 8.
- Total weight =
2 * 1 + 3 * 8 = 26 - Total cost =
2 * 2 + 3 * 11 = 37
Therefore, the minimum total cost is 37.
Example 2
Input:
cost = [3, 10, 20]
minWeight = 5Output:
23Explanation:
One optimal selection consists of two items of weight 2 and one item of weight 1.
- Total weight =
2 * 2 + 1 = 5 - Total cost =
2 * 10 + 3 = 23
Alternatively, one item of weight 4 and one item of weight 1 also provide a total weight of 5 at a cost of 20 + 3 = 23.
Therefore, the minimum total cost is 23.
Constraints
1 <= cost.length <= 301 <= cost[i] <= 10^91 <= minWeight <= 10^9
Additional conditions:
- The weight of the item at index
iis2^i. - An unlimited number of items of each available weight can be purchased.
- The total weight of the selected items must be greater than or equal to
minWeight.
Follow-up
Can you solve this problem in O(n) time and O(1) auxiliary space?
Topics
Greedy, Dynamic Programming, Bit Manipulation, Optimization