> This can be done efficiently via, eg, Dijkstra’s algorithm, but since this is such a small graph, we can also easily enumerate all 36 paths and sort for efficiency.
Brute force enumeration for small problem instances is pragmatic. For larger problems, Dijkstra's algorithm would certainly work, and would also work for more general problems where we're given a graph containing cycles.
For this barbell plate problem we could also exploit the acyclic structure and use bottom-up dynamic programming: maintain a table tracking the cost of the cheapest path to each node, and an auxiliary table tracking the predecessor node or incoming edge per node where the cheapest path was attained, then fill out the tables "bottom up" (or left to right per the diagrams). Less general, but it dodges the need to do a bunch of work maintaining a priority queue of partial paths.
Another fun connection is to the Viterbi algorithm - a completely different real world application to barbell plate optimization - decoding a sequence of noisy observations and trying to reconstruct the most probable trajectory of unobserved states - but the abstract mathematical model & way to attack it computationally is very similar -- construct a DAG, a solution is a least-cost path through the DAG (ignoring all the problem-specific details going into the definition of state spaces, transition graphs, edge costs, etc). c.f. "The Viterbi Algorithm at 50 (2017)" from a couple of months ago: https://news.ycombinator.com/item?id=35897851
edit: i guess another connection is the knapsack problem mentioned in this post -- it can also be framed as a least-cost path through a DAG, and computed bottom-up.
For this barbell plate optimisation problem, the acyclic structure comes from the monotonic increasing sequence of goal weights. For the Viterbi algorithm's problem of inferring a most probable sequence, the acyclic structure comes from each observation being ordered by the observation time. For the knapsack problem, there isn't really a natural problem defined ordering of item take/leave decisions, but the decisions can be sequenced in any arbitrary fixed order.
Brute force enumeration for small problem instances is pragmatic. For larger problems, Dijkstra's algorithm would certainly work, and would also work for more general problems where we're given a graph containing cycles.
For this barbell plate problem we could also exploit the acyclic structure and use bottom-up dynamic programming: maintain a table tracking the cost of the cheapest path to each node, and an auxiliary table tracking the predecessor node or incoming edge per node where the cheapest path was attained, then fill out the tables "bottom up" (or left to right per the diagrams). Less general, but it dodges the need to do a bunch of work maintaining a priority queue of partial paths.
Another fun connection is to the Viterbi algorithm - a completely different real world application to barbell plate optimization - decoding a sequence of noisy observations and trying to reconstruct the most probable trajectory of unobserved states - but the abstract mathematical model & way to attack it computationally is very similar -- construct a DAG, a solution is a least-cost path through the DAG (ignoring all the problem-specific details going into the definition of state spaces, transition graphs, edge costs, etc). c.f. "The Viterbi Algorithm at 50 (2017)" from a couple of months ago: https://news.ycombinator.com/item?id=35897851
edit: i guess another connection is the knapsack problem mentioned in this post -- it can also be framed as a least-cost path through a DAG, and computed bottom-up.
For this barbell plate optimisation problem, the acyclic structure comes from the monotonic increasing sequence of goal weights. For the Viterbi algorithm's problem of inferring a most probable sequence, the acyclic structure comes from each observation being ordered by the observation time. For the knapsack problem, there isn't really a natural problem defined ordering of item take/leave decisions, but the decisions can be sequenced in any arbitrary fixed order.