What does Knapsacks, Inspection Games and the Customs Reversal Point conclude, in numbers, about “One Suitcase as a Two-Dimensional Knapsack: Weight, Volume and the Price of Greedy Density”?
Answer: Chapter 1 writes a checked bag of 23 kg and 100 litres as a two-dimensional 0-1 knapsack; dynamic programming finds a best margin of 10460 yuan, while greedy packing by margin per kilogram reaches only 0.9254 of it.
Scope of the numbers: Its parameters are illustrative and laws differ from place to place; all calculations are generated by its programs; the book is not individual legal or tax advice. Marked boxes separate published evidence, runnable Python calculations (19 programs), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 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 |
Show the full program
# 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))Single source and citation
Fan, Y. (2026). Two-Dimensional Volume-Weight Knapsacks for Cross-Border Buyers, Port Risk-Profiling Inspection Games and the Scale Reversal Point to Formal Customs Clearance (Version 1.0.0), Chapter 1: One Suitcase as a Two-Dimensional Knapsack: Weight, Volume and the Price of Greedy Density. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 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}
}Other chapter answers in this book
- Chapter 2 · The Larger of Actual and Volumetric Weight: Break-Even Density, Mixed Loads and Vacuum Packing
- Chapter 3 · The Border as an Inspection Game: Mixed Equilibria of Declaring and Risk Profiling
- Chapter 4 · The Nonlinearity of Hidden Penalties: Back Taxes, Confiscation, Tracing and Credit
- Chapter 5 · The Scale Reversal Point: Landed Cost of Carrying, Cross-Border E-Commerce and General Trade
- Chapter 6 · Tail Risk in a Year of Cash Flow and the Landed-Cost Calculator
- Chapter 7 · Classical Sources: the Salt Policy of the Guanzi "Hai Wang" and Smith's Smuggler
- Chapter 8 · Practice and Falsification: Checklists for Buyers and Owners, the Calculator and a Pre-Registered Protocol