0 Replies - 29356 Views - Last Post: 21 December 2012 - 09:58 PM Rate Topic: -----

#1 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon

Reputation: 12315
  • View blog
  • Posts: 45,414
  • Joined: 27-December 08

A Look at the Knapsack Problem with Generating Functions

Posted 21 December 2012 - 09:58 PM

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:

Attached Image

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.

Attached Image

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

Attached Image

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:
Attached Image

Attached Image

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

Attached Image

Attached Image

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

Attached Image

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 xr is important as it represents the inventory, or quantity to fill in the knapsack. The coefficient of xr 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 x2 should be in the series. If 50 2's are an option, then multiply x2 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:
Attached Image

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)4. The coefficient of interest is that associated with x25, as the Knapsack quantity is 25.

Based on the second binomial identity, the coefficient of x25 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 x0 or x1 terms as no variable can take on the value of 0 or 1.
Attached Image

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 x2 from a given term, which amounts to x8. The generating function is now easier to simplify leaving us with:
f(x) = x8 * 1/(1-x)4.

As x8 has been factored out, the coefficient of interest is now x17 instead of x25. 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 x17.

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 + x2 + x3 + x4 + x5 + x6). Exponentiate this to the 8th, since there are 8 dice.

This leaves the function as follows, with x26 as the coefficient of interest:
f(x) = (x + x2 + x3 + x4 + x5 + x6)8.

To simplify the generating function, we can factor out x from each individual term. This leaves:
f(x) = x8 * (1 + x + x2 + x3 + x4 + x5)8

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

Expanding out (1-x6)8, we get:
a(x) = 1 - C(8, 1) * x6 + C(8, 2) * x12 - C(8, 3) * x18

This series could be expanded further, but the coefficient of interest is x18, as x8 has been factored out.

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

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)

Is This A Good Question/Topic? 3
  • +

Page 1 of 1