The Knapsack Problem

ICMS

Page:

Demo

THE DYNAMIC PROGRAMMING ALGORITHM

One way of solving the knapsack problem is to simply run through all possible combinations. But this method is not practical if the number of objects involved is large.

We use dynamic programming techniques to solve this problem in an efficient manner. We illustrate the algorithm used with an example (from the cutting stock problem).

You are establishing a gambling casino and the floor space available is limited to 250 sq. yards. The games you want to set up are Baccarat, Blackjack, Roulette and Poker. The estimated space (1 unit = 10 sq. yards) required and utility value per table are as follows:

Utility value per table
Game	Space Per table	First Table	Second Table	Third Table	Fourth Table
1) Baccarat	4	10	7	4	1
2) Blackjack	5	9	9	8	8
3) Roulette	6	11	10	9	8
4) Poker	3	8	6	4	2

As more tables are added, the utility values of the tables decrease. If more than one table of a game is available, the clientele may tend to use one table all the time and the other tables may then be idle part of the time.

How many tables of each game should be set up to maximize the expected profit?

The algorithm we use solves this problem as follows:

Let a_j = space required per table of the j^th game;

d_j = number of tables taken of the j^th game;

v_j(d_j) = total utility of d_j tables of the j^th game;

and A = total floor area available = 25 units.

The number of games, n, is 4. We handle the problem in n stages.

At any stage k, we consider only the first k games, and maximize the utility achievable using only these k games.

Suppose we are at the k^th stage and the space available is S.

d_k tables of the k^th game require d_ka_k units of space. Therefore, the space available for the first k 1 objects is

S d_ka_k.

We include d_k tables of the k^th game only if the utility of these tables [v_k(d_k)] plus the maximum utility achieved by using the first k 1 games to fill the remaining space (S d_ka_k) exceeds the maximum utility achievable using only the first k 1 games to fill the whole space S.