knapsack has a size and a benefit. The problem is to determine what should go into the knapsack to maximise the total benefit The travelling salesperson problem: in this problem a salesperson must visit a number of cities with a minimum distance or cost. The alternatives are which of the next cities he/she travels to when located in a given city. The cities are separated by distances, time or cost, which must be minimised. The equipment replacement problem: in this problem, a given piece of equip- ment (a machine, a car, etc.) is to be used during successive time periods (months, years, etc.). This equipment has its corresponding running and main- tenance costs, which may increase with time. As the equipment becomes older, and its running costs go up, it must be replaced after a given time. For this replacement, a new piece of equipment is purchased (one that is at least not as old as the current one) and the current one is sold, resulting in a net cost for the purchasing cost of a new piece of equipment miss the sale price of the current . in equipment There are numerous algorithms which employ dynamic programming to solve problems in different science and business areas: Backward induction (Aumann 1995), attice models for protein-DNA binding (Lengauer 1993), the Cocke- Younger-Kasami algorithm (Cocke and Schwartz 1970). (Kasami 1965). (Youn- ger 1967), the Viterbi algorithm (Viterbi 1967), the Earley algorithm (Earley 1970), the Needleman-Wunsch algorithm (Needleman and Wunsch 1970), etc. The model that the Introduction describes is a deterministic dynamic pro- gramming model in which given a state and a decision, both the immediate payoff 9.1 Introduction 329 and next state are known. If we know either of these only as a probability function, then we have a stochastic dynamic programme. The basic ideas of determining stages, states, decisions and recursive formulae still hold: they simply take into account uncertainties (uncertain payoff or uncertain states). After reading this chapter, readers should be able to: comprehend the nature of multiphase decision problems that can be modelled by dynamic programming: define the stages of the problem, its input stages and the decisions that can be made; define the transition function between the input state and the output stage according to the decision made in each stage: construct the recursive function of a dynamic programming model. Calculate the optimal costs in each stage, as well as the optimal decisions. Obtain the optimal solutions that provide dynamic pro- gramming for decision making. 9.2 Commercialisation of Products Sold Under Licence The director of a chain of sports stores, AdeMark, is studying the possibility of acquiring a maximum of five licences to sell five sport brand names (Nike, Adidas, Reebok, SportBall and Avia) so they can be commercialised among three stores. The expected profits depend on the brand marks offered in each store, and are provided in Table 9.1. (a) Determine how to distribute the five sales licences of the sport brand names