Understanding the counting knapsack pattern

A large family of problems hands us a set of items and a single capacity, and asks us to count the number of ways the items can fill that capacity exactly, with every item available in unlimited supply. Counting the number of ways to make change for an amount, counting the number of ways to climb a staircase with moves of fixed sizes, or counting the sets of pieces that assemble a rod length, are all problems of this kind.

Problems like these are solved by the counting knapsack technique, a variation of the unbounded knapsack technique where the operator pair counts the number of ways instead of optimising a value. We decide the items one at a time, and everything the problem counts is assembled along a path of these decisions.

The input is a set of n items given as an array weights, where the item at index i carries a weight weights[i] that says how much of the capacity it consumes. Along with the items we are given a single capacity C, the target that the chosen weights must fill.

In this lesson we will learn what a way really means, the counting knapsack technique, why it qualifies as a dynamic programming problem, and how to solve it both top-down and bottom-up.

What counting really means

Two problems can both ask to count the number of ways and still mean different things by a way. A way can be a permutation, a sequence of items where the same items in a different order are two different sequences, or it can be a unique combination, a selection of items where the order means nothing and the same items count as one selection regardless of the order.