关于「时段装箱:首次适配降序的 11/9 界、精确动态规划与碎片档期空置率」,《摄影场馆的装箱、退改与折旧》给出的定量结论是什么?

结论:第一章用一维装箱说明,首次适配降序在对抗实例上达到 1.2222 的比值,在随机订单簿上平均只比最优多用很少的棚日,而最小空置拼接在不改价格的前提下使售出份额提高 0.0457。

数据口径:书中参数为示意;全部计算由书中程序生成;本书不是个人化的税务、法律或投资建议。 书中以标注框区分已发表的证据、可运行的 Python 计算(22 段程序)、原典与作者的假说。

English version

对照数据表

下表数字由本章 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}
}

本书其他章节结论