Balancing Wants and Constraints: Navigating the Knapsack Problem

Introduction:
Imagine that you are packing for holiday and you have to pack but you have constraints with respect to the bag that the airline allows you to carry. The goal should be pack the most valuable items. Our focal point: the Knapsack Problem, a puzzle of choice and capacity

Problem Definition:
To maximize the total value of items you can pack, considering the below table with the list of items, their individual weight and worth.

Your challenge is to strategically select a combination of items from the list to maximize the total value while staying within a strict weight limit. Your backpack can only hold items with a total weight of 15 units.

METHOD 1: Excel Solver

Set-up:

• The Decision variable are the items that would be considered for packing. Its a binary variable (Highlighted in Yellow cells)

• The objective function is to maximize the total weight that could be carried (sum of the selected weight of the items).

Solution:

METHOD 2: Python Code

import pulp
# Create the problem
prob = pulp.LpProblem("KnapsackProblem", pulp.LpMaximize)
# Data
items = [
    {"name": "A", "weight": 12, "value": 4},
    {"name": "B", "weight": 2, "value": 2},
    {"name": "C", "weight": 1, "value": 2},
    {"name": "D", "weight": 1, "value": 1},
    {"name": "E", "weight": 4, "value": 10}
]
# Decision variables
pick = {item["name"]: pulp.LpVariable(item["name"], cat='Binary') for item in items}
# Objective function: maximize total value
prob += pulp.lpSum([pick[item["name"]] * item["value"] for item in items])
# Constraint: total weight should be less than or equal to 15
prob += pulp.lpSum([pick[item["name"]] * item["weight"] for item in items]) <= 15
# Solve the problem
prob.solve()
# Print the results
print("Status:", pulp.LpStatus[prob.status])
print("Total Value:", pulp.value(prob.objective))
print("Picked Items:")
for item in items:
    if pick[item["name"]].value() == 1:
        print(f"{item['name']} - Weight: {item['weight']}, Value: {item['value']}")

Solution:
Status: Optimal
Total Value: 15.0
Picked Items:
B - Weight: 2, Value: 2
C - Weight: 1, Value: 2
D - Weight: 1, Value: 1
E - Weight: 4, Value: 10

Navigating the delicate balance between wants and limitations is an essential skill in both problem-solving and real-life scenarios. Stay curious, keep optimizing, and remember that the path to value maximization is often found in the delicate art of balancing

Further Reads:

1. KNAPSACK Problem
2. Packing problem