cs-143 — The Shelf Replenishment

Problem

A corner shop has 20 shelves. One assistant visits each shelf once per day, in a fixed order, and can restock only what fits in their cart (capacity 30 units). Each shelf sells a known number of units per day:

shelf:   A  B  C  D  E  F  G  H  I  J
per day: 9  5  7  3  8  2  6  4  5  6

(shelves K–T total 41 units/day more, same structure). A shelf must never reach zero during the day: sales happen after the assistant's visit. The cart is refilled to 30 units at the start of each day.

Your deliverables:

1. The restock rule the assistant follows each day (in words, then as two lines of pseudocode).
2. Worked check on shelf A: does your rule keep A stocked all day, every day, with daily visits? Show one day.
3. The failure case: which shelf goes empty first if visits drop to every second day, and why the rule cannot save it?
4. The trade-off sentence: capacity 30 vs daily cadence — which would you negotiate first, and what evidence for it?

If the problem is ambiguous anywhere, state the assumption you are making and carry on — a stated assumption is part of a good answer.

Examples

• Input: per-day sales rates, cart capacity 30, cadence 1 day
• Output: a rule of the form "restock shelf X to at least 2× its daily rate" — shelf A safe — and the identified failure shelf under cadence 2

Solve for the worked instance first. Then ask what would change if one number, name, or condition were replaced by something stranger.

What to notice

• "Never empty before the next visit" converts directly into a target: stock after a visit must cover sales until the next visit, with margin for the day's swing.
• The binding constraint is the pair (capacity, cadence): halving the cadence doubles the required per-visit stock, and some shelf's demand will exceed what a cart of 30 can carry.
• A rule that works for one shelf but needs the cart to carry 90 units is not a rule — check the total against capacity.

Discussion starter

After the solution is revealed, the class spends five minutes on this prompt: "Management offers a second assistant who can start mid-day but carries only 15 units. Model the effect on your rule's binding constraint in two sentences — no full simulation needed."

Constraints and assumptions

• Difficulty: Intermediate (constraint reasoning across a small system).
• Topics: inventory, greedy, trade-offs.
• Sales are steady at the stated per-day rate; no spikes this week.
• Classroom-scale inputs unless the problem says otherwise.
• Time-box: about five minutes for a first attempt; partial answers with clear reasoning are worth more than silent struggling.
• Optional stretch (not required): describe an alternative approach and say when it beats the obvious one.

Hints and extension

• First nudge: write shelf A's "stock at close" equation in terms of its restock amount.
• If stuck after three minutes, write the input/output line you expect and trace the smallest example by hand.
• After the reveal, attempt the extension below before the next lecture.
• Extension challenge: express the minimum cart capacity as a formula in the per-day rates and the cadence — then check it against the ten shelves given.