Module day17 

No Such Thing as Too Much

Given n items the number of possible subsets is 2ⁿ. We could brute force through each subset by iterating from 0 to 2ⁿ using the binary bits to indicate if a container is present. This will work but is a little slow as there are 20 containers, giving 2²⁰ = 1048576 combinations to check.

Part One

Tackling this with dynamic programming provides a much faster approach. We build a table similar to but not exactly the same as the knapsack problem. This approach is built atop a solution provided by e_blake preserved in the commit history.

The table has target + 1 columns and containers + 1 rows. Each table[row, col] is computed row by row from the sum of:

• Not taking the current item, using just the existing number of ways to make the target table[row - 1, col]
• Taking the current item, using the existing number of ways to make the target weight less the weight of the current item table[row - 1, col - item].

The table for the example looks like:

    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] Initial
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0] 20
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0] 15
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1] 10
    [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2] First 5
    [1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 3, 0, 0, 0, 0, 4, 0, 0, 0, 0, 4] Second 5

The answer 4 is the bottom right cell. Since only the previous row is needed to compute the current row, we optimize by only storing a single row instead of the entire table and updating in place.

Part Two

The key insight is to keep two tables. The first table tracks the number of combinations as before. The second table tracks the minimum number of containers needed to store each volume up to and including the target size.

If taking the item results in fewer containers then we add that number of combinations. Vice-versa if not taking the item results in fewer containers then we don’t include it. If both taking and not taking the item results in the same number of containers then we add both.

The new minima table for the example using u32::MAX to represent ∞ is:

    [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] Initial
    [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, ∞] 20
    [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, ∞] 15
    [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 2] 10
    [0, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 2] First 5
    [0, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 2] Second 5

The minimum number of containers needed to make the target is the bottom right cell (2). The combinations table with the minimum restriction is:

    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] Initial
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0] 20
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0] 15
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1] 10
    [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2] First 5
    [1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3] Second 5

Functions

parse

part1

part2

part1_testable

part2_testable