# Maximize cost in graph with variable costs

Consider the following problem. A prisoner eats once a day, he can either have a low, or a high calorie dish. In order to be allowed to eat the high calorie dish, he must not have eaten the previous day. The prisoner knows the calories of each dish for the full week, and wishes to maximize his calorie intake for the week.

I modeled the problem into a bidirected cyclic graph: l[n], h[n] are the two known arrays of costs and k the number of steps taken through the graph. (The cost to the H node at the kth step is h[k]). L represents eating the low nutrient dish, while H the high one. If you want to get to H you must pass from - first and amass no cost. The costs represent the nutrients gained when moving to each node. (They could be rewards on the nodes instead). S is the start node. The goal is to maximize the cost, given the number of maximum steps n. I'm looking for a general direction. Does it belong to a known family of problems? If yes, how do you solve them efficiently? Dynamic programming, knapsack or some known modification of a graph traversal algorithm? Is considering it a graph problem wrong, or not particulartly helpful? Sorry for the barrage of questions.

• I don't understand what your graph represents. What states are represented by the vertices? What do the weights mean? You mention costs but I'm not sure what the costs are: the set-up has a benefit (the amount of calories eaten in a particular day) but I don't see any costs involved. Also, if it's literally that this is done week-by-week, there are only $3^7\approx 2200$ possibilities and a computer can trivially try all of those without any real need for finesse. – David Richerby Jun 1 '16 at 17:52
• The week was an example, where k=7. The problem must be solved for k=n. I edited my question to better explain what the graph respresents. If you have any questions/corrections let me know. – potis Jun 2 '16 at 17:03

## 1 Answer

There's no need to introduce a graph; the problem can be solved by a straightforward dynamic programming algorithm. The running time will be $O(n)$, where $n$ is the number of days.

• That was my thought in the beggining, but how do I break this into subproblems that dont affect one another? Am I wrong in thinking that's a requirement for a dynamic programming algorithm? – potis Jun 2 '16 at 17:05