Complexity and Tractability

Resources

https://www.csfieldguide.org.nz/en/chapters/complexity-and-tractability/

https://heidi-newton.com/blog/introducing-the-knapsack-problem-in-a-classroom

Lesson 1 & 2 Background Understanding

Complete tasks 1 to 4

Read the following

Read through and complete 11.1 of the CSFG What's the big picture?

Read through and complete 11.2 of the CSFG Algorithms, problems, and speed limits

Read through and complete 11.2 of the CSFG Tractability

TASK 1

Each card represents an item in a (fictional) RPG (Role-Play Game). Each item has a weight in KG and a value in gold. The character controlled by the player has found these items in the terrifying fire-breathing dragon's lair and wants to take them back to the shop at the surface to sell for gold. However, there's a big problem—they can only carry up to 6 KG's at a time, otherwise, should they encounter the dragon, they'll never have a chance of outrunning it. Unfortunately, making multiple trips to the shop is not an option, as the dragon will be sure to ensure there won't be any return trips anytime soon.

Which items should be taken, and which should be left behind? Remember, we want to make as much gold as we can, and we cannot carry any more than 6 KG. There is only one of each item, and anything left behind cannot be claimed later.

TASK 2

This time, the character is in a different dungeon, and can carry up to 30 KG's.

Which items should be taken, and which should be left behind? Remember, we want to make as much gold as we can, and we cannot carry any more than 30 KG. There is only one of each item, and anything left behind cannot be claimed later.

Question : How are you doing this - what is you algorithm?

TASK 3

This time, the theme is a cargo plane that has room for another 5000 KG and wants to maximize the value of what it is carrying. The third set of cards.

What is your solution? Are you sure it is correct? Did you follow the same algorithm as in Tasks 1 & 2?

TASK 4

This time, the theme is investments. Each of the 20 investments has an amount that would need to be put forward to invest in it, and an expected pay off. With $2000 to invest, the challenge now is to decide which investments to choose.

Some follow up points

We call this problem the Knapsack Problem. Precisely, the Knapsack Problem is where we have the following 3 things:

1. Some items, each of which has a burden, such as a weight, and a value, such as a profit.
2. A constraint in the form of "the total added burdens must not exceed..."
3. A need to maximize the total added values while staying below the constraint.

In the RPG theme, the burden of an item was its weight, the value was how much gold it was worth, and the constraint was to keep the total weight of all items at or below what the character could carry.

Likewise, in the cargo theme, the burden of an item was also its weight, the value was how much profit could be made by carrying that item, and the constraint was to keep the total weight at or below what the plane could carry.