from ortools.sat.python import cp_model

SHIPS = 5
SHIP_CAP = 100
FREE_CAP = 20
shipments = [(20, 6), (15, 6), (30, 4), (45, 3)]

model = cp_model.CpModel()

# n[k, s] = number of shipments of size k in ship s
n = {}
for (size, count) in shipments:
    for s in range(SHIPS):
        n[size, s] = model.NewIntVar(0, count, f'size {size} shipment on ship {s}')

# Each shipment is on exactly one ship
for (size, count) in shipments:
    model.Add(
        sum(n[size, s] for s in range(SHIPS)) == count
    )

# Respect capacity constraints
for s in range(SHIPS):
    model.Add(
       sum(size * n[size, s] for (size, _) in shipments) <= SHIP_CAP
    )

# Want to maximize number of ships with 20 free capacity
# ship_free[s] = True iff ship s has >= 20 free capacity
ship_free = {}
for s in range(SHIPS):
    ship_free[s] = model.NewBoolVar(f'ship {s} has enough free capacity')
    ship_load = sum(size * n[size, s] for (size, _) in shipments)

    model.Add(ship_load <= SHIP_CAP - FREE_CAP).OnlyEnforceIf(ship_free[s])
    model.Add(ship_load > SHIP_CAP - FREE_CAP).OnlyEnforceIf(ship_free[s].Not())

model.Maximize(sum(ship_free.values()))

solver = cp_model.CpSolver()
if solver.Solve(model) == cp_model.OPTIMAL:
    print([f'{solver.Value(v)} {v}' for v in n.values() if solver.Value(v)])
    print(solver.ResponseStats())