Sometimes you can know people for years and never really understand them. Take your friends Raj and Alanis, for example. Neither of them is a morning person, but now they’re getting up at 6 AM every day to visit local farmers’ markets, gathering fresh fruits and vegetables for the new health-food restaurant they’ve opened, Chez Alanisse.

In the course of trying to save money on ingredients, they’ve come across the following thorny problem. There is a large set of n possible raw ingredients they could buy, I₁, I₂,..., I_n (e.g., bundles of dandelion greens, jugs of rice vinegar, and so forth). Ingredient Ij must be purchased in units of size s(j) grams (any purchase must be for a whole number of units), and it costs c(j) dollars per unit. Also, it remains safe to use for t(j) days from the date of purchase.

Now, over the next k days, they want to make a set of k different daily specials, one each day. (The order in which they schedule the specials is up to them.) The i^th daily special uses a subset S_i ⊆ {I₁, I₂,..., I_n} of the raw ingredients. Specifically, it requires a(i, j) grams of ingredient I_j. And there’s a final constraint: The restaurant’s rabidly loyal customer base only remains rabidly loyal if they’re being served the freshest meals available; so for each daily special, the ingredients Si are partitioned into two subsets: those that must be purchased on the very day when the daily special is being offered, and those that can be used any day while they’re still safe. (For example, the mesclun-basil salad special needs to be made with basil that has been purchased that day; but the arugula-basil pesto with Cornell dairy goat cheese special can use basil that is several days old, as long as it is still safe.)

This is where the opportunity to save money on ingredients comes up. Often, when they buy a unit of a certain ingredient I_j, they don’t need the whole thing for the special they’re making that day. Thus, if they can follow up quickly with another special that uses I_j but doesn’t require it to be fresh that day, then they can save money by not having to purchase I_j again. Of course, scheduling the basil recipes close together may make it harder to schedule the goat cheese recipes close together, and so forth— this is where the complexity comes in.

So we define the Daily Special Scheduling Problem as follows: Given data on ingredients and recipes as above, and a budget x, is there a way to schedule the k daily specials so that the total money spent on ingredients over the course of all k days is at most x?

Prove that Daily Special Scheduling is NP-complete.