The densest item left the sack half empty

# Self-authored for the EML case corpus (no external origin). A loader fills a
# ten-kilo sack by taking items in order of value per kilo, never exceeds the
# weight limit, and every item it takes is worth exactly what it says. How much
# value that rule packs, against how much the sack could hold, is computed below.
#
# The rule is careful. It reads the real weights and values; it ranks exactly by
# value per kilo; it never exceeds the limit; and the intent is exactly 'pack
# the most value the sack can carry'.
#
# The densest item is six kilos and nothing else fits beside it, while two
# slightly less dense five-kilo items fill the sack exactly - so the densest
# item packs 60 where the sack could hold 90.

10 => capacity_kg
6 => x_weight
60 => x_value
5 => y_weight
45 => y_value
5 => z_weight
45 => z_value

int(x_value * 10 / x_weight) => x_value_per_kg_tenths
int(y_value * 10 / y_weight) => y_value_per_kg_tenths
x_value => greedy_value_packed
capacity_kg - x_weight => space_left_after_x
y_value + z_value => optimal_value_packed
y_weight + z_weight => optimal_weight_used
optimal_value_packed - greedy_value_packed => value_left_behind
int(greedy_value_packed * 10000 / optimal_value_packed) => greedy_share_of_the_optimum_per_myriad

"sack capacity                   : " + str(capacity_kg) + " kg" ^0
"item X                          : " + str(x_weight) + " kg, value " + str(x_value) + ", " + str(x_value_per_kg_tenths) + " tenths per kg" ^0
"item Y                          : " + str(y_weight) + " kg, value " + str(y_value) + ", " + str(y_value_per_kg_tenths) + " tenths per kg" ^0
"item Z                          : " + str(z_weight) + " kg, value " + str(z_value) + ", " + str(y_value_per_kg_tenths) + " tenths per kg" ^0
"" ^0
"densest first                   : X, then " + str(space_left_after_x) + " kg left, nothing fits" ^0
"value packed, densest first     : " + str(greedy_value_packed) ^0
"best packing                    : Y and Z, " + str(optimal_weight_used) + " kg, value " + str(optimal_value_packed) ^0
"value left behind               : " + str(value_left_behind) ^0
"share of the optimum reached    : " + str(greedy_share_of_the_optimum_per_myriad) + " per ten thousand" ^0
"" ^0

# ---- what the rule verified ----

"the densest-first rule" ^0
"  reads : the real weights and values" ^0
"  ranks : exactly by value per kilo" ^0
"  limit : never exceeded" ^0
"  intent : pack the most value the sack can carry" ^0
"  overweight sacks : 0" ^0
"  verdict : THE DENSEST ITEM IS PACKED FIRST" ^0
"" ^0
"  ranking exactly by density and never exceeding the limit" ^0
"  is the part done right here, and it is why the sack is" ^0
"  never overweight and the first pick is never wrong per kilo" ^0
"" ^0

# ---- what density does not see ----

"the greedy choice" ^0
"  X per kilo : best, " + str(x_value_per_kg_tenths) + " tenths" ^0
"  X in the sack : " + str(x_weight) + " kg, leaving " + str(space_left_after_x) + " that no item fits" ^0
"  Y and Z per kilo : slightly worse, " + str(y_value_per_kg_tenths) + " tenths" ^0
"  Y and Z in the sack : " + str(optimal_weight_used) + " kg, the sack exactly full" ^0
"  what density ranks : each item alone" ^0
"  what the sack rewards : the combination that leaves no" ^0
"    kilo empty" ^0
"" ^0

# ---- what the loader got ----

"the sack" ^0
"  value carried : " + str(greedy_value_packed) ^0
"  value it could have carried : " + str(optimal_value_packed) ^0
"  kilos wasted : " + str(space_left_after_x) ^0
"  is any pick wrong per kilo : no; X is the best per kilo" ^0
"  is the best-per-kilo set the best set : no; it is the" ^0
"    best first pick and the worst finish" ^0
"" ^0

# ---- null control ----

# The same items packed by considering combinations that fill the capacity,
# not items ranked one at a time.
60 => nc_value_by_densest_first
90 => nc_value_by_best_combination
30 => nc_value_the_combination_recovers

"null control - choose the combination, not the item" ^0
"  value, densest first : " + str(nc_value_by_densest_first) ^0
"  value, best combination : " + str(nc_value_by_best_combination) ^0
"  value the combination recovers : " + str(nc_value_the_combination_recovers) ^0
"  no item and no sack changed; the rule stopped scoring" ^0
"  items one at a time" ^0
"" ^0

# ---- the rule ----

"what a densest-item-first packing guarantees" ^0
"  each item taken is the best remaining per kilo : exactly," ^0
"    real weights and values, exact ranking" ^0
"  the sack carries the most value it can : not addressed;" ^0
"    the densest item leaves " + str(space_left_after_x) + " kg nothing fits, so it packs " + str(greedy_value_packed) ^0
"    where two lighter items pack " + str(optimal_value_packed) ^0
"" ^0

"the best item and the best load are different questions; a rule that ranks" ^0
"pieces on their own cannot see the space each one leaves, and the piece that" ^0
"scores highest alone can be the one that spoils the fit for everything after it" ^0
"" ^0

"It ranks exactly by value per kilo and never exceeds the limit - the first pick" ^0
"is the best per kilo. But X leaves " + str(space_left_after_x) + " kg that nothing fits, so the sack" ^0
"carries " + str(greedy_value_packed) + " where Y and Z would carry " + str(optimal_value_packed) + ", " + str(greedy_share_of_the_optimum_per_myriad) + " per ten thousand of the" ^0
"optimum, until the loader chooses the combination and not the item." ^0

capacity_kg = 10
x_weight = 6
x_value = 60
y_weight = 5
y_value = 45
z_weight = 5
z_value = 45
x_value_per_kg_tenths = int(x_value * 10 / x_weight)
y_value_per_kg_tenths = int(y_value * 10 / y_weight)
greedy_value_packed = x_value
space_left_after_x = capacity_kg - x_weight
optimal_value_packed = y_value + z_value
optimal_weight_used = y_weight + z_weight
value_left_behind = optimal_value_packed - greedy_value_packed
greedy_share_of_the_optimum_per_myriad = int(greedy_value_packed * 10000 / optimal_value_packed)
print("sack capacity                   : " + str(capacity_kg) + " kg")
print("item X                          : " + str(x_weight) + " kg, value " + str(x_value) + ", " + str(x_value_per_kg_tenths) + " tenths per kg")
print("item Y                          : " + str(y_weight) + " kg, value " + str(y_value) + ", " + str(y_value_per_kg_tenths) + " tenths per kg")
print("item Z                          : " + str(z_weight) + " kg, value " + str(z_value) + ", " + str(y_value_per_kg_tenths) + " tenths per kg")
print("")
print("densest first                   : X, then " + str(space_left_after_x) + " kg left, nothing fits")
print("value packed, densest first     : " + str(greedy_value_packed))
print("best packing                    : Y and Z, " + str(optimal_weight_used) + " kg, value " + str(optimal_value_packed))
print("value left behind               : " + str(value_left_behind))
print("share of the optimum reached    : " + str(greedy_share_of_the_optimum_per_myriad) + " per ten thousand")
print("")
print("the densest-first rule")
print("  reads : the real weights and values")
print("  ranks : exactly by value per kilo")
print("  limit : never exceeded")
print("  intent : pack the most value the sack can carry")
print("  overweight sacks : 0")
print("  verdict : THE DENSEST ITEM IS PACKED FIRST")
print("")
print("  ranking exactly by density and never exceeding the limit")
print("  is the part done right here, and it is why the sack is")
print("  never overweight and the first pick is never wrong per kilo")
print("")
print("the greedy choice")
print("  X per kilo : best, " + str(x_value_per_kg_tenths) + " tenths")
print("  X in the sack : " + str(x_weight) + " kg, leaving " + str(space_left_after_x) + " that no item fits")
print("  Y and Z per kilo : slightly worse, " + str(y_value_per_kg_tenths) + " tenths")
print("  Y and Z in the sack : " + str(optimal_weight_used) + " kg, the sack exactly full")
print("  what density ranks : each item alone")
print("  what the sack rewards : the combination that leaves no")
print("    kilo empty")
print("")
print("the sack")
print("  value carried : " + str(greedy_value_packed))
print("  value it could have carried : " + str(optimal_value_packed))
print("  kilos wasted : " + str(space_left_after_x))
print("  is any pick wrong per kilo : no; X is the best per kilo")
print("  is the best-per-kilo set the best set : no; it is the")
print("    best first pick and the worst finish")
print("")
nc_value_by_densest_first = 60
nc_value_by_best_combination = 90
nc_value_the_combination_recovers = 30
print("null control - choose the combination, not the item")
print("  value, densest first : " + str(nc_value_by_densest_first))
print("  value, best combination : " + str(nc_value_by_best_combination))
print("  value the combination recovers : " + str(nc_value_the_combination_recovers))
print("  no item and no sack changed; the rule stopped scoring")
print("  items one at a time")
print("")
print("what a densest-item-first packing guarantees")
print("  each item taken is the best remaining per kilo : exactly,")
print("    real weights and values, exact ranking")
print("  the sack carries the most value it can : not addressed;")
print("    the densest item leaves " + str(space_left_after_x) + " kg nothing fits, so it packs " + str(greedy_value_packed))
print("    where two lighter items pack " + str(optimal_value_packed))
print("")
print("the best item and the best load are different questions; a rule that ranks")
print("pieces on their own cannot see the space each one leaves, and the piece that")
print("scores highest alone can be the one that spoils the fit for everything after it")
print("")
print("It ranks exactly by value per kilo and never exceeds the limit - the first pick")
print("is the best per kilo. But X leaves " + str(space_left_after_x) + " kg that nothing fits, so the sack")
print("carries " + str(greedy_value_packed) + " where Y and Z would carry " + str(optimal_value_packed) + ", " + str(greedy_share_of_the_optimum_per_myriad) + " per ten thousand of the")
print("optimum, until the loader chooses the combination and not the item.")

sack capacity                   : 10 kg
item X                          : 6 kg, value 60, 100 tenths per kg
item Y                          : 5 kg, value 45, 90 tenths per kg
item Z                          : 5 kg, value 45, 90 tenths per kg

densest first                   : X, then 4 kg left, nothing fits
value packed, densest first     : 60
best packing                    : Y and Z, 10 kg, value 90
value left behind               : 30
share of the optimum reached    : 6666 per ten thousand

the densest-first rule
  reads : the real weights and values
  ranks : exactly by value per kilo
  limit : never exceeded
  intent : pack the most value the sack can carry
  overweight sacks : 0
  verdict : THE DENSEST ITEM IS PACKED FIRST

  ranking exactly by density and never exceeding the limit
  is the part done right here, and it is why the sack is
  never overweight and the first pick is never wrong per kilo

the greedy choice
  X per kilo : best, 100 tenths
  X in the sack : 6 kg, leaving 4 that no item fits
  Y and Z per kilo : slightly worse, 90 tenths
  Y and Z in the sack : 10 kg, the sack exactly full
  what density ranks : each item alone
  what the sack rewards : the combination that leaves no
    kilo empty

the sack
  value carried : 60
  value it could have carried : 90
  kilos wasted : 4
  is any pick wrong per kilo : no; X is the best per kilo
  is the best-per-kilo set the best set : no; it is the
    best first pick and the worst finish

null control - choose the combination, not the item
  value, densest first : 60
  value, best combination : 90
  value the combination recovers : 30
  no item and no sack changed; the rule stopped scoring
  items one at a time

what a densest-item-first packing guarantees
  each item taken is the best remaining per kilo : exactly,
    real weights and values, exact ranking
  the sack carries the most value it can : not addressed;
    the densest item leaves 4 kg nothing fits, so it packs 60
    where two lighter items pack 90

the best item and the best load are different questions; a rule that ranks
pieces on their own cannot see the space each one leaves, and the piece that
scores highest alone can be the one that spoils the fit for everything after it

It ranks exactly by value per kilo and never exceeds the limit - the first pick
is the best per kilo. But X leaves 4 kg that nothing fits, so the sack
carries 60 where Y and Z would carry 90, 6666 per ten thousand of the
optimum, until the loader chooses the combination and not the item.

Trace event types