[macosxnerd101]

The Knapsack Problem- Generating Functions

The Knapsack Problem is a combinatorial optimization problem, to determine if a quantity can be produced given a set of base values. Diophantine equations and the change problem are two common forms of the Knapsack Problem. This tutorial will explore the Knapsack Tutorial through the use of generating functions.

As a caveat, generating functions are very abstract. As part of this tutorial, a refresher on geometric series will be included. If you do not have a strong background with series manipulations as it is, you may struggle with generating functions.

Refresher on Geometric Series
A Geometric Series grows based on a ratio raised to an exponent. It is convergent if the ratio is less than one. Some examples of geometric series are as follows:

The general form:




An example of a convergent series is below. Notice how that the ratio is less than 1, so as it is exponentiated repeatedly, it goes to 0, which is why the series converges.




Inversely, this geometric series diverges, as the ratio is not less than 1.




For the purpose of working with generating functions, it is assumed that the series either converges or a portion of the series is being examined. For those cases, we have the following identities:





Important Identities
Before moving onto using generating functions to solve problems, there are two important identities left:







Generating Functions
Generating functions take a specific form of a geometric series as follows:



Generating functions are not meant to be evaluated at specific values of x. Instead, there are two components of interest: the exponent of x and the coefficient of said term.

The exponent r in the term x^r is important as it represents the inventory, or quantity to fill in the knapsack. The coefficient of x^r describes the number of ways to fulfill the knapsack quantity.

The approach when solving them is as follows:
-Set up the individual terms, to represent the available choices. Remember that a power of x represents the inventory. So if a value of 2 is an option, then x² should be in the series. If 50 2's are an option, then multiply x² by 50. If a value of 0 is an option, simply include a 1.

-Next, multiply the terms together. Then try and apply geometric series and binomial identities. Use the binomial identities to solve for the given coefficient.

The approach is definitely abstract, so let's work through a few examples.


Consider the following example:
1) Find the generating function for the Diophantine equation w + x + y + z = 25.

Let's start by examining a single variable. There have been no restrictions on the values it can take on, so the geometric series goes to infinity:


Since there are four variables with the same choices, raise the series to the fourth. By the Geometric Series identity presented in the last section, we know that f(x) = 1/(1-x)⁴. The coefficient of interest is that associated with x²⁵, as the Knapsack quantity is 25.

Based on the second binomial identity, the coefficient of x²⁵ is C(25 + 4 - 1, 25).

2) Now let's add constraints on the above problem: Let each variable be at least 2. So that changes the geometric series for a single term in the following way. There are no x⁰ or x¹ terms as no variable can take on the value of 0 or 1.


We still exponentiate it to the fourth, as there are four terms.

Now let's simplify the series. To start, we can factor out an x² from a given term, which amounts to x⁸. The generating function is now easier to simplify leaving us with:
f(x) = x⁸ * 1/(1-x)⁴.

As x⁸ has been factored out, the coefficient of interest is now x¹⁷ instead of x²⁵. Looking at the original Diophantine equation:
w + x + y + z = 25, with each variable >= 2.

Now shift each variable to be >= 0, so subtract 8 from the Knapsack quantity of 25 to get:
w + x + y + z = 17

Since there is no top term, again refer back to the second binomial identity to find the coefficient of x¹⁷.

The number of solutions = C(17 + 4 - 1, 17).


3) Let's consider one final example:
Given 8 six-sided dice, how many ways are there to roll a 26.

Since the dice each have values 1-6, the geometric series cannot go to infinity. So for a given term, the generating function is (x + x² + x³ + x⁴ + x⁵ + x⁶). Exponentiate this to the 8th, since there are 8 dice.

This leaves the function as follows, with x²⁶ as the coefficient of interest:
f(x) = (x + x² + x³ + x⁴ + x⁵ + x⁶)⁸.

To simplify the generating function, we can factor out x from each individual term. This leaves:
f(x) = x⁸ * (1 + x + x² + x³ + x⁴ + x⁵)⁸

Applying the geometric series identities, the generating function can be rewritten as:
f(x) = x⁸ * [(1-x⁶) / (1-x)]⁸

Expanding out (1-x⁶)⁸, we get:
a(x) = 1 - C(8, 1) * x⁶ + C(8, 2) * x¹² - C(8, 3) * x¹⁸

This series could be expanded further, but the coefficient of interest is x¹⁸, as x⁸ has been factored out.

Next, expand out the term 1/(1-x))⁸:
b(x) = 1 + C(1 + 8 - 1, 1) * x + C(2 + 8 - 1, 2) * x² + ...

As f(x) = a(x) * b(x), it is easy to get intimidated with a massive polynomial expansion. This is rather unnecessary. Instead, it is only necessary to cross-multiply so that the power of x is 18.

This leaves us with our answer:
1 * C(18 + 8 - 1, 18) - C(8, 1) * C(12 + 8 - 1, 12) + C(8, 2) * C(6 + 8 - 1, 6) - C(8, 3)