Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
- Considering only hotdog packs
~h_1, \dots, h_i~, let 
~\operatorname{opt}_h(i, k)~ denote the minimum number of packs you need to buy to have exactly 
~k~ hotdogs, or 
~+\infty~ if impossible.
- Similarly, let
~\operatorname{opt}_b(i, k)~ denote the corresponding value for the packs of buns 
~b_1, \dots, b_i~.
- If
~C = \min\left(\sum_{i=1}^H h_i, \sum_{i=1}^B b_i\right)~, the answer is:
$$\displaystyle \min_{1 \le k \le C} \operatorname{opt}_b(B, k) + \operatorname{opt}_h(H, k)$$
- Note that
~C \le 100 \cdot 1\,000 = 10^5~.
- Computing ~\operatorname{opt}_h(i, k)~ is an instance of the Knapsack problem (or a variant thereof), and can be solved in a similar manner as follows.
- Based on whether we buy the
~i^\text{th}~ pack of hotdogs (
~h_i~) or not, we get the following recurrence:
$$\displaystyle \operatorname{opt}_h(i, k) = \min(1 + \operatorname{opt}_h(i-1, k-h_i), \operatorname{opt}_h(i-1, k))$$
- We also have the base cases:
$$\displaystyle \operatorname{opt}_h(i, k) = \begin{cases}0 & \text{if }k = 0 \\ +\infty & \text{if }i = 0\text{ or }k < 0\end{cases}$$
- We have a similar recursion for ~\operatorname{opt}_b(i, k)~.
- Finally,
~\operatorname{opt}_h(H, k)~ and 
~\operatorname{opt}_b(B, k)~ can be computed for all 
~1 \le k \le C~ in 
~\mathcal O((B+H)C)~ using dynamic programming (or memoization).
Comments