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
rulemarginshare of DPkg usedlitresunits
exact DP104601.000021.710032
greedy per kg96800.925414.810026
greedy per litre104500.999021.29832
greedy combined104500.999021.29832
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