Abby is a researcher at a company that makes chemical solutions. Her boss left her with a difficult task late Friday afternoon, and waltzed off into the weekend.
Abby has a hazardous liquid that reacts with oxygen by exploding. Her task is to distribute the liquid between special containers. The company buys containers of specific sizes in bulk, so she has access to a lot of containers of each size.
Since the liquid is explosive, Abby needs to fill the containers full to the exact capacity. Preparing the containers is tricky, so Abby wants to use as few containers as possible. Given the
totalAmount of liquid and the set of container sizes
containers, find the total number of containers she will need.
If there’s no way to distribute the liquid as described above, return
totalAmount = 18and
containers = [1, 2, 5, 10],
the output should be
Chemicals(totalAmount, containers) = 4.Abby has access to containers with sizes
1, and will use one container of each size.
totalAmount = 9and
containers = [1, 4, 6],
the output should be
Chemicals(totalAmount, containers) = 3.Abby can use two containers of size
4and one container of size
- [time limit] 4000ms (py)
- [input] integer totalAmountThe amount of chemicals.Guaranteed constraints:
0 ≤ totalAmount < 5 · 104.
- [input] array.integer containersA sorted array of distinct integers, denoting the container sizes.Guaranteed constraints:
1 ≤ containers.length ≤ 15,
0 ≤ containers[i] ≤ 1000.
- [output] integerThe minimum number of containers needed to distribute the liquid. Return
-1if there’s no way to distribute the liquid.
def Chemicals(totalAmount, containers): totalAmount+=1 d=*totalAmount d=0 for x in containers: if x <totalAmount: d[x]= 1 for x in range(totalAmount): for y in containers: if x-y>0: d[x]= min(d[x],d[x-y]+1) if d[-1]==999999: return -1 return d[-1]
Knapsack Problem, you can search for this term and learn more about it. In essence, create an array d. Each element of d shows the best solution up to that index. The idea follows this:
If I can get maximum value of 90 at 10 weight, and I have an item with weight 2 and value 10, then, at the best case, I can have 100 value at 92.
Reversing this, we want to minimize our weight at a given value. And slightly modifying the problem, we want to minimize number of containers at a given value.
If I can use minimum 5 containers to store 90, and I have containers of size 5, then I can have minimum 6 containers for size 95.