Dynamic programming is especially helpful for problems where there are many different options and we have a particular goal we’re trying to maximize.
For the sake of learning, we’re going to imagine ourselves as burglars. We’ve broken into someone’s home and there are many different things we can steal.
Each item has a weight and a value. Our goal is to maximize the total value of items while remaining within the weight we can fit in our knapsack.
This is another ideal situation to apply dynamic programming, but to start we’ll use the brute force approach and generate every single possible combination.
We can total each combination’s weight and value to find the most lucrative collection.
To help, we’re given a Loot
class with name
, weight
, and value
properties.
computer = Loot("Computer", 2, 12) print(computer) # Computer: # weighs 2, # valued at 12,
We also have a powerset()
function which creates a list of all combinations.
fruits = ['apple', 'orange', 'grape'] fruit_combinations = power_set(fruits) print(fruit_combinations) #[(), ('apple',), ('orange',), ('grape',), ('apple', 'orange'), ('apple', 'grape'), ('orange', 'grape'), ('apple', 'orange', 'grape')]
Note: Codecademy does not endorse thievery!
Instructions
We’ll start our function by setting up our combinations of loot.
After best_value
, declare all_combo
.
We now have two variables:
all_combo
: Usepowerset()
to create all combinations of theloot
argument.best_value
: Tracks the best loot combination. Initialized atNone
.
Iterate through each combo
in all_combo
.
Inside the loop, create two new variables:
combo_weight
: The sum of all loot weight incombo
.combo_value
: The sum of all loot value incombo
.
Remember, each combo
is a list of Loot
instances. We can use a list comprehension to pull out certain properties.
combo_names = [item.name for item in combo]
We can use sum()
to get a total from a list:
nums = [5, 3, 1] sum(nums) # 9
With combo_weight
and combo_value
, we can make informed decisions about what to take.
Check if combo_weight
fits in the knapsack. combo_weight
will fit if it’s less than or equal to weight_limit
.
If it does fit, we need to check to see if it’s the best value we’ve seen.
It’s the best value we’ve seen if best_value
is still set to None
OR combo_value
is greater than best_value
.
Here’s a pseudo-code breakdown:
# if {the combination fits} # if {there isn't a best value} or # {combo value greater than best} # set best_value to be combo_value
All the hard work is done!
When the loop concludes, check if best_value
is None
.
If so, print "knapsack couldn't fit any items"
.