关于「时段装箱:首次适配降序的 11/9 界、精确动态规划与碎片档期空置率」,《摄影场馆的装箱、退改与折旧》给出的定量结论是什么?
结论:第一章用一维装箱说明,首次适配降序在对抗实例上达到 1.2222 的比值,在随机订单簿上平均只比最优多用很少的棚日,而最小空置拼接在不改价格的前提下使售出份额提高 0.0457。
数据口径:书中参数为示意;全部计算由书中程序生成;本书不是个人化的税务、法律或投资建议。 书中以标注框区分已发表的证据、可运行的 Python 计算(22 段程序)、原典与作者的假说。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 1.2222
A. adversarial book: 30 orders, total 540 units, capacity 60 lower bound 9, OPT 9 (31+16+13 x6, 17+17+13+13 x3), FFD 11 Dosa bound 11/9*OPT+6/9 = 11.667; ratio FFD/OPT = 1.2222 B. 1500 random books of 9 orders, day = 24 half-hours NF mean studio-days 3.8660 FF mean studio-days 3.5840 FFD mean studio-days 3.4807 OPT mean studio-days 3.4453 FFD above OPT in 53 books (0.0353); worst ratio 1.5000 books breaking 11/9*OPT+6/9: 0; at OPT 2 the bound is 3.111 idle share FFD 0.1523, OPT 0.1432
查看完整验算程序
# Chapter 1. p11: first fit decreasing against the exact optimum.
# A studio-day is a bin of 24 half-hour units (09:00 to 21:00). Orders
# whose start can float inside the day are items. Part A packs the
# classic adversarial order book (capacity 60 units of 12 minutes;
# items 31, 17, 16 and 13 units) to show FFD = 11 against OPT = 9.
# Part B draws random order books of 9 orders, packs them by next fit,
# first fit in arrival order and FFD, and finds the exact optimum by
# a subset dynamic programme. Durations are illustrative.
import math
import random
def first_fit(items, cap):
bins = []
for s in items:
for i, b in enumerate(bins):
if b + s <= cap:
bins[i] = b + s
break
else:
bins.append(s)
return len(bins)
def next_fit(items, cap):
n, room = 0, 0
for s in items:
if s > room:
n, room = n + 1, cap
room -= s
return n
def exact(items, cap):
n = len(items)
best = [None] * (1 << n)
best[0] = (1, 0)
for mask in range(1, 1 << n):
cand = None
for i in range(n):
if mask >> i & 1:
b, f = best[mask ^ (1 << i)]
s = items[i]
st = (b, f + s) if f + s <= cap else (b + 1, s)
if cand is None or st < cand:
cand = st
best[mask] = cand
return best[-1][0]
hard = [31] * 6 + [17] * 6 + [16] * 6 + [13] * 12
lb = math.ceil(math.fsum(hard) / 60)
print("A. adversarial book: 30 orders, total {} units, capacity 60".format(
int(math.fsum(hard))))
print(" lower bound {}, OPT 9 (31+16+13 x6, 17+17+13+13 x3), FFD {}"
.format(lb, first_fit(sorted(hard, reverse=True), 60)))
print(" Dosa bound 11/9*OPT+6/9 = {:.3f}; ratio FFD/OPT = {:.4f}".format(
11 / 9 * 9 + 6 / 9, 11 / 9))
rng = random.Random(20261112)
menu = [3, 4, 4, 6, 6, 8, 8, 9, 10, 12, 16]
C, N, T = 24, 9, 1500
tot = {"NF": [], "FF": [], "FFD": [], "OPT": []}
worse, vac_ffd, vac_opt, mx, viol = 0, [], [], 0.0, 0
for _ in range(T):
it = [rng.choice(menu) for _ in range(N)]
ffd = first_fit(sorted(it, reverse=True), C)
low = math.ceil(math.fsum(it) / C)
opt = ffd if ffd == low else exact(sorted(it, reverse=True), C)
tot["NF"].append(next_fit(it, C))
tot["FF"].append(first_fit(it, C))
tot["FFD"].append(ffd)
tot["OPT"].append(opt)
worse += ffd > opt
viol += ffd > 11 / 9 * opt + 6 / 9
mx = max(mx, ffd / opt)
vac_ffd.append(1 - math.fsum(it) / (ffd * C))
vac_opt.append(1 - math.fsum(it) / (opt * C))
print("B. {} random books of {} orders, day = {} half-hours".format(T, N, C))
for k in ("NF", "FF", "FFD", "OPT"):
print(" {:4s} mean studio-days {:.4f}".format(k, math.fsum(tot[k]) / T))
print(" FFD above OPT in {} books ({:.4f}); worst ratio {:.4f}".format(
worse, worse / T, mx))
print(" books breaking 11/9*OPT+6/9: {}; at OPT 2 the bound is {:.3f}"
.format(viol, 11 / 9 * 2 + 6 / 9))
print(" idle share FFD {:.4f}, OPT {:.4f}".format(
math.fsum(vac_ffd) / T, math.fsum(vac_opt) / T))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《多规格实景空间时段一维装箱、动态退改期权阶梯与高损耗器材加速折旧运筹》第 1 章「时段装箱:首次适配降序的 11/9 界、精确动态规划与碎片档期空置率」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-173 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026173,
author = {Fan, Yafu},
title = {One-Dimensional Time-Slot Packing for Multi-Format Studio Sets, Dynamic Cancellation-Option Ladders and Accelerated Depreciation of High-Wear Equipment},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}