Learn
Technical Interview Problems: Dynamic Programming
Knapsack Without Memoization

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

1.

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: Use powerset() to create all combinations of the loot argument.
  • best_value: Tracks the best loot combination. Initialized at None.
2.

Iterate through each combo in all_combo.

Inside the loop, create two new variables:

  • combo_weight: The sum of all loot weight in combo.
  • combo_value: The sum of all loot value in combo.

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
3.

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
4.

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".

Folder Icon

Sign up to start coding

Already have an account?