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