HLPL / VerTeX Modelling Language Documentation

← lessons

Knapsack — add the capacity

One constraint, everything changes.

Chapter: VI — Knapsack · lesson id knapsack-capacity · practice lesson

---

Now the bag. Each item has a weight w_i, and total weight can't exceed W. Add a single constraint to the model from the previous lesson — and now the solver has to make trade-offs.

Items with weights [2, 3, 4, 2, 1] and capacity W = 6. Which subset wins?

Predict before running

Values {6,4,5,3,2}, weights {2,3,4,2,1}, capacity 6. Which items win?

• Items 1, 2, 5. Value 12, weight 6
• Items 1, 3. Value 11, weight 6
• Items 1, 2, 4. Value 13, weight 7

Starter code

model knap
bin x1
bin x2
bin x3
bin x4
bin x5
constr 2*x1 + 3*x2 + 4*x3 + 2*x4 + 1*x5 <= 6
max 6*x1 + 4*x2 + 5*x3 + 3*x4 + 2*x5
end

import elytica
def main():
  elytica.init_model("knap")
  elytica.run_model("knap")
  for i in [1,2,3,4,5]:
    print("x"+str(i), "=", elytica.get_variable_value("knap", "x"+str(i)))
  print("obj =", elytica.get_best_primal_bound("knap"))
  return 0

Hint

The capacity is 6. Items {1, 2, 5} weigh 2+3+1 = 6 — fits exactly, value 6+4+2 = 12.

What counts as correct

• no-error — Model solves
• numeric-match — Optimal value is 12 (items 1, 2, and 5)
• numeric-match — Item 1 is in
• numeric-match — Item 5 is in
• code-contains — Reads the objective from the solver (no hardcoding)
• code-contains — Reads variable values from the solver (no hardcoding)

Mastery variant

New values, weights, and a tighter bag. Which three items pack best now?

model knap_v
bin x1
bin x2
bin x3
bin x4
bin x5
constr 3*x1 + 2*x2 + 4*x3 + 1*x4 + 2*x5 <= 7
max 8*x1 + 5*x2 + 7*x3 + 4*x4 + 3*x5
end

import elytica
def main():
  elytica.init_model("knap_v")
  elytica.run_model("knap_v")
  for i in [1,2,3,4,5]:
    print("x"+str(i), "=", elytica.get_variable_value("knap_v", "x"+str(i)))
  print("obj =", elytica.get_best_primal_bound("knap_v"))
  return 0

Read this through MCP: read with path: "lessons/knapsack-capacity", or resource hlpl://lessons/knapsack-capacity.