Tom Hundley
🤖 Ghostwritten by Claude Opus 4.6 · Fact-checked & edited by GPT 5.4
When a trip includes multiple hotel stays and a limited points balance, the best redemption strategy is not "use points whenever possible." It is to allocate points only where they produce the most value relative to cash. In practice, that maps cleanly to a 0/1 knapsack problem: each stay has a points cost, a cash alternative, and a measurable redemption value; the budget is the total points balance. Solve the optimization exactly, and the system can recommend which stays should use points and which should be paid in cash.
This article explains that optimization model, why a greedy heuristic is not enough for binary hotel redemptions, how date normalization avoided a subtle time-zone bug, and why a hard human approval gate matters whenever software recommends actions with financial consequences.
TL;DR: Not all redemptions are equally valuable, so spending points opportunistically can waste scarce rewards on low-value stays.
Hotel loyalty programs generally price award stays in points while cash rates fluctuate by market, season, event demand, taxes, and cancellation terms. That means the same points outlay can produce very different redemption value from one stay to the next.
A simple way to compare options is cents per point (cpp):
cpp = cash price in cents / points required
If one stay returns 0.4 cpp and another returns 1.2 cpp, redeeming points on the first stay may crowd out a much better use later in the trip. That is the core failure mode of a naive strategy such as "I have enough points for tonight, so I should use them."
A practical optimizer usually needs a baseline valuation: a floor below which redeeming points is not attractive. Here, the working baseline is approximately 0.7 cents per point. That is directionally consistent with many third-party valuations for major hotel programs, though exact values vary by program and over time.
Rather than treating the threshold as a hard truth, it is better understood as a configurable planning assumption. In the model, each candidate stay gets a score based on how much it exceeds the baseline. Stays below the threshold default toward cash; stays above it compete for the limited points budget.
That framing matters because the goal is not merely to find redemptions above 0.7 cpp. It is to maximize total surplus value across the whole itinerary.
TL;DR: For whole-stay redemptions, exact 0/1 knapsack is the right model because each stay is all-or-nothing and the points budget is finite.
The classic 0/1 knapsack problem asks: given a set of items, each with a weight and a value, which subset maximizes total value without exceeding capacity?
For hotel redemptions, the mapping is straightforward:
| Knapsack concept | Trip-planning mapping |
|---|---|
| Item | A candidate hotel stay |
| Weight | Points required for that stay |
| Value | Redemption value above the baseline |
| Capacity | Total available points budget |
| Solution | Which stays use points and which use cash |
A useful implementation detail: if value is defined as (cpp - baseline) * points_required, that simplifies algebraically to cash_price_cents - baseline * points_required. This avoids mixing a ratio with a budgeted objective and produces a total score in cents of surplus value.
A greedy heuristic can be fast, but for 0/1 knapsack it does not guarantee an optimal answer. That matters because hotel stays are indivisible in this model: a stay is either booked with points or it is not.
The article's original example did not actually show a greedy failure, so it has been tightened below with a case that does:
A greedy strategy that picks the highest-value item first chooses Leg A for a total surplus value of 35,000. But the exact solution chooses Leg B + Leg C, which fits the same 50,000-point budget and yields 39,000. Greedy loses.
That is why exact optimization is justified here. For modest itinerary sizes, it is computationally cheap and removes guesswork.
def recommend_points_allocation(legs, points_budget, cpp_baseline=0.7):
"""Exact 0/1 knapsack over candidate redemptions."""
candidates = []
for leg in legs:
cpp = leg.cash_price_cents / leg.points_required
if cpp > cpp_baseline:
candidates.append({
"leg": leg,
"weight": leg.points_required,
"value": leg.cash_price_cents - (cpp_baseline * leg.points_required)
})
n = len(candidates)
W = points_budget
dp = [[0.0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w_i = candidates[i - 1]["weight"]
v_i = candidates[i - 1]["value"]
for w in range(W + 1):
dp[i][w] = dp[i - 1][w]
if w_i <= w:
dp[i][w] = max(dp[i][w], dp[i - 1][w - w_i] + v_i)
selected = []
w = W
for i in range(n, 0, -1):
if dp[i][w] != dp[i - 1][w]:
selected.append(candidates[i - 1]["leg"])
w -= candidates[i - 1]["weight"]
points_used = sum(c["weight"] for c in candidates if c["leg"] in selected)
return {
"redeem_with_points": selected,
"pay_cash": [l for l in legs if l not in selected],
"points_used": points_used,
"points_banked": points_budget - points_used
}The pseudo-code above is illustrative, not production code. In a real system, the main engineering choices are usually around scaling and data quality rather than the recurrence itself. A full O(n * W) dynamic program is reasonable when the number of stays is small and the points budget is bounded, but teams often reduce the state space further by rounding point values, using sparse DP, or switching to branch-and-bound if budgets become large.
TL;DR: Date-only hotel stays can drift by a day when mixed with timestamps, so normalization must be explicit and consistent.
Hotel bookings are usually expressed as calendar dates: check-in and check-out. Rate feeds and APIs, however, often arrive as timestamps. If one source treats a stay as a local date and another serializes it as UTC, comparisons can slip by one day around time-zone boundaries.
The original article described a fix of anchoring dates to noon UTC. That can work as an internal normalization strategy, but the claim that "no inhabited time zone can push it across a date boundary" is too strong. As of 2026, inhabited time zones span offsets from UTC−12 to UTC+14, so noon UTC can still map to the next local calendar day in UTC+13 and UTC+14.
A more precise takeaway is this: if the business object is a date, the safest approach is to keep it as a date-only value throughout the pipeline. If a timestamp is required for storage or comparison, the system should choose one canonical convention and apply it consistently, while testing edge cases across the full range of relevant time zones. Noon UTC may reduce some off-by-one risks compared with midnight UTC, but it is not universally boundary-proof.
TL;DR: Any system that recommends spending money or points should separate recommendation from execution and require explicit human approval.
Optimization is useful; autonomous financial action is riskier. A parser bug, stale rate, room mismatch, or policy edge case can turn a mathematically correct recommendation into a bad booking decision.
The architecture described here uses a hard separation between analysis and execution:
That separation is sound engineering. It limits blast radius, improves auditability, and makes it easier to review why a recommendation was made before any irreversible step occurs.
TL;DR: The main design questions are about exactness, valuation, date handling, and operational safety.
Because hotel redemptions are discrete. You cannot usually redeem points for half a stay in a way that preserves the same economics, so the fractional version of knapsack does not apply. If the itinerary is small, exact optimization is usually affordable and removes avoidable error.
No. It is a planning baseline, not a law of nature. Different hotel programs have different average redemption patterns, and elite benefits, taxes, resort fees, and cancellation flexibility can all change the effective value of a redemption.
Usually yes, if the goal is to compare the real out-of-pocket cost of cash versus points. But the answer depends on the program. Some award stays still incur taxes or fees, while others waive more of the total bill. The comparison should use like-for-like totals.
That can be a good choice if the entire pipeline is date-centric and property-local. Problems arise when one subsystem stores local dates, another stores UTC timestamps, and a third compares them as if they were interchangeable. The key is consistency, not blind preference for UTC.
Yes, with caveats. The optimization pattern transfers, but airline awards often introduce more constraints: transfer partners, dynamic pricing, mixed-cabin itineraries, and schedule risk. The math still works, but the scoring model usually needs more inputs.
The interesting part of this system is not that it uses a famous algorithm. It is that a familiar optimization technique becomes genuinely useful only when the surrounding assumptions are disciplined: comparable cash totals, a configurable points valuation, careful date handling, and a strict separation between recommendation and execution. Get those pieces right, and a points budget stops being something to spend opportunistically and becomes something to allocate deliberately.
Discover more content: