The Knapsack Problem

What Is an Optimization Problem?

An optimization problem means finding the best possible solution from many choices.

Usually, “best” means:

• Maximum value (largest profit, highest score, most items)
• Minimum value (lowest cost, shortest time, least waste)

Real-Life Examples

• Fastest route to school
• Cheapest way to ship packages
• Most points in fantasy sports under a salary cap
• Best schedule using limited time

How Do We Solve Optimization Problems?

Ask these two questions:

A. What are we trying to optimize?

Are we trying to:

• maximize something?
• minimize something?

​

B. What are the constraints?

Constraints are the rules or limits.

Examples:

• weight limit
• budget limit
• time limit
• space limit

​

Example: Traffic Lights

A city wants traffic lights to move cars efficiently.

Goal:

Maximize the number of cars that pass each hour.

Constraints:

• red lights must last long enough
• yellow lights needed for safety
• side streets also need turns
• timing must repeat in a cycle

The Knapsack Problem

Imagine you have a backpack with a weight limit.

You have several items. Each item has:

• a weight
• a value

You want to choose items so that:

• total weight does not go over the limit
• total value is as large as possible

​

Example

Question:

Which items should you take?

​

What are we maximizing?

→ Total value

What is the constraint?

→ Total weight ≤ limit

​

Backpack limit = 10 kg

| Item | Weight | Value |

| ------ | ------ | ----- |

| Laptop | 6 | 9 |

| Camera | 4 | 7 |

| Jacket | 3 | 5 |

| Snacks | 2 | 4 |

​

Challenge:

If you could only carry 7 kg, what items would you choose?

Solutions to the Knapsack Problem

Shown in class:

• Knapsack Problem - Brute Force Solution

​

Watch on your own:

• Greedy Algorithm to solve the 0/1 Knapsack Problem
• Recursive Solution to the 0/1 Knapsack Problem

​

​

Now do Lab 7 - the Grocery Problem.