## The Problem:

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 `-1`

instead.

**Example**

- For
`totalAmount = 18`

and`containers = [1, 2, 5, 10]`

,

the output should be

`Chemicals(totalAmount, containers) = 4`

.Abby has access to containers with sizes`10`

,`5`

,`2`

, and`1`

, and will use one container of each size. - For
`totalAmount = 9`

and`containers = [1, 4, 6]`

,

the output should be

`Chemicals(totalAmount, containers) = 3`

.Abby can use two containers of size`4`

and one container of size`1`

.

**Input/Output**

**[time limit] 4000ms (py)**

**[input] integer totalAmount**The amount of chemicals.*Guaranteed constraints:*

`0 ≤ totalAmount < 5 · 10`

.^{4}**[input] array.integer containers**A sorted array of distinct integers, denoting the container sizes.*Guaranteed constraints:*

`1 ≤ containers.length ≤ 15`

,

`0 ≤ containers[i] ≤ 1000`

.**[output] integer**The minimum number of containers needed to distribute the liquid. Return`-1`

if there’s no way to distribute the liquid.

## The Solution:

def Chemicals(totalAmount, containers): totalAmount+=1 d=[999999]*totalAmount d[0]=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]

## The Explanation:

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.