def knapsack_ilp(items, maxweight, verbose=False):
    import pulp
    values  = [t[0] for t in items]
    weights = [t[1] for t in items]
    indices = [t[2] for t in items]
    prob = pulp.LpProblem("Knapsack", pulp.LpMaximize)
    x = pulp.LpVariable.dicts(name='x', indexs=indices,
                              lowBound=0, upBound=1, cat=pulp.LpInteger)
    prob.objective = sum(v * x[i] for v, i in zip(values, indices))
    prob.add(sum(w * x[i] for w, i in zip(weights, indices)) <= maxweight)
    pulp.PULP_CBC_CMD().solve(prob)
    flags = [x[i].varValue for i in indices]
    total_value = sum([val for val, flag in zip(values, flags) if flag])
    items_subset = [item for item, flag in zip(items, flags) if flag]
    if verbose:
        print(prob)
        print('OPT:')
        print('\n'.join(['    %s = %s' % (x[i].name, x[i].varValue) for i in indices]))
        print('total_value = %r' % (total_value,))
    return total_value, items_subset