关于「一只箱子的二维背包:重量、体积与价值密度贪心的代价」,《买手的背包、口岸博弈与报关反转点》给出的定量结论是什么?
结论:第一章把一只 23 公斤、100 升的托运箱写成二维 0-1 背包,动态规划的最优毛利是 10460 元,按每公斤毛利贪心只得到 0.9254。
数据口径:书中参数为示意,各地法规不同;全部计算由书中程序生成;本书不是个人化的法律或税务建议。 第三章把口岸查验写成检查博弈,示意参数下不申报的盈亏平衡查验率是 0.1852,而风险画像使查验率在每季度两到四趟之间从 0.0380 跳到 0.5035。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.9254, 100, 10460, 23
| units on offer 40, bag 23 kg x 100 litres | |||||
| rule | margin | share of DP | kg used | litres | units |
| exact DP | 10460 | 1.0000 | 21.7 | 100 | 32 |
| greedy per kg | 9680 | 0.9254 | 14.8 | 100 | 26 |
| greedy per litre | 10450 | 0.9990 | 21.2 | 98 | 32 |
| greedy combined | 10450 | 0.9990 | 21.2 | 98 | 32 |
| DP packs: cream 3, formula 1, handbag 3, headphones 3, lipstick 3, | |||||
| perfume 3, serum 3, sneakers 3, tea tin 3, vitamins 2, watch 2, wine 3 |
查看完整验算程序
# Chapter 1. p11: one suitcase as a two-dimensional 0-1 knapsack.
# A buyer chooses which units to pack into one checked bag limited to
# 23 kg and 100 litres. Each unit has a weight, a volume and a gross
# margin (resale price minus purchase price, before any tax or travel
# cost). Exact dynamic programming over (0.1 kg, 1 litre) cells is
# compared with three greedy rules that sort by value density: margin
# per kg, margin per litre, and margin per "combined share" w/W + v/V.
# Catalogue and margins are illustrative, in yuan; not market data.
import math
import textwrap
W, V = 230, 100 # capacity in 0.1 kg and in litres
CAT = [ # name, 0.1 kg, litres, margin yuan, copies available
("serum", 3, 1, 260, 3), ("cream", 4, 1, 210, 3),
("perfume", 5, 1, 240, 3), ("lipstick", 2, 1, 90, 3),
("sneakers", 13, 9, 420, 3), ("handbag", 11, 12, 900, 3),
("down coat", 10, 15, 380, 3), ("watch", 4, 1, 1100, 2),
("formula", 9, 3, 70, 3), ("vitamins", 4, 1, 60, 3),
("wine", 15, 2, 150, 3), ("headphones", 6, 2, 300, 3),
("kettle", 18, 6, 160, 2), ("tea tin", 5, 2, 120, 3),
]
items = []
for name, w, v, m, c in CAT:
items += [(name, w, v, m)] * c
def exact(items):
best = [[0] * (V + 1) for _ in range(W + 1)]
keep = []
for _, w, v, m in items:
k = bytearray((W + 1) * (V + 1))
for a in range(W, w - 1, -1):
row, src = best[a], best[a - w]
for b in range(V, v - 1, -1):
cand = src[b - v] + m
if cand > row[b]:
row[b] = cand
k[a * (V + 1) + b] = 1
keep.append(k)
a, b, pick = W, V, []
for i in range(len(items) - 1, -1, -1):
if keep[i][a * (V + 1) + b]:
pick.append(i)
a -= items[i][1]
b -= items[i][2]
return best[W][V], pick
def greedy(items, key):
order = sorted(range(len(items)), key=lambda i: (-key(items[i]), i))
a = b = val = 0
pick = []
for i in order:
_, w, v, m = items[i]
if a + w <= W and b + v <= V:
a, b, val = a + w, b + v, val + m
pick.append(i)
return val, pick
def load(pick):
kg = math.fsum(items[i][1] for i in pick) / 10
lit = math.fsum(items[i][2] for i in pick)
return kg, lit
opt, pk = exact(items)
rules = [("per kg", lambda t: t[3] / t[1]),
("per litre", lambda t: t[3] / t[2]),
("combined", lambda t: t[3] / (t[1] / W + t[2] / V))]
print("units on offer {}, bag 23 kg x 100 litres".format(len(items)))
print("rule margin share of DP kg used litres units")
kg, lit = load(pk)
print("{:16s}{:8d} 1.0000 {:7.1f} {:7.0f} {:6d}"
.format("exact DP", opt, kg, lit, len(pk)))
for lab, f in rules:
g, gp = greedy(items, f)
kg, lit = load(gp)
print("{:16s}{:8d} {:.4f} {:7.1f} {:7.0f} {:6d}"
.format("greedy " + lab, g, g / opt, kg, lit, len(gp)))
names = {}
for i in pk:
names[items[i][0]] = names.get(items[i][0], 0) + 1
txt = "DP packs: " + ", ".join("{} {}".format(n, names[n])
for n in sorted(names))
print(textwrap.fill(txt, 72))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《跨国买手体积重量双维背包优化、口岸风险画像抽检博弈与正规报关规模反转点》第 1 章「一只箱子的二维背包:重量、体积与价值密度贪心的代价」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-174 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026174,
author = {Fan, Yafu},
title = {Two-Dimensional Volume-Weight Knapsacks for Cross-Border Buyers, Port Risk-Profiling Inspection Games and the Scale Reversal Point to Formal Customs Clearance},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}