Dynamic Programming21 sections · 916 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.