Dynamic Programming21 sections · 915 units
Open in Course

Tall Barn - Penalized DP

The formulation

Add penalty λ\lambda per cow. New goal: reduce ∑i=1Nai/ci+λ⋅Kused\sum_{i=1}^{N} a_i / c_i + \lambda \cdot K_{used}. For each floor ii with work aia_i, compute the optimal number of cows to assign if each cow costs λ\lambda.

This is a separate improvement per floor! For floor ii: reduce ai/c+λ⋅ca_i / c + \lambda \cdot c over positive integers cc. The optimal cc is around ai/λ\sqrt{a_i / \lambda}. Try c=⌊ai/λ⌋c = \lfloor\sqrt{a_i / \lambda}\rfloor and c+1c+1, take the better one.