The Knapsack Problem

ICMS

Page:

Demo

Let F_k(S) denote the maximum utility that can be achieved from a space limitation S using only the first k items. S can take values from 0 to A.

We obtain the following recursion formula:

F_k(S) = max { v_k(d_k) + F_k-1(S d_ka_k) , F_k-1(S)} as d_k varies from 0 to number of tables available.

We now describe the stepwise solution to our problem. At every stage the columns 0 to 25 represent the space available at that stage and the rows 0 to 4 represent the number of tables we select of that game. The numbers in the table give us the utility for that particular combination of row (d = number of tables) and column (S = space available).

STAGE 1: Game: Baccarat Space occupied per table: 4 units Utility Values: 10, 7, 4, 1.

d\S	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
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	0	0
1	¾	¾	¾	¾	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10
2	¾	¾	¾	¾	¾	¾	¾	¾	17	17	17	17	17	17	17	17	17	17	17	17	17	17	17	17	17	17
3	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	21	21	21	21	21	21	21	21	21	21	21	21	21	21
4	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	22	22	22	22	22	22	22	22	22	22
F₁	0	0	0	0	10	10	10	10	17	17	17	17	21	21	21	21	22	22	22	22	22	22	22	22	22	22
d₁	0	0	0	0	1	1	1	1	2	2	2	2	3	3	3	3	4	4	4	4	4	4	4	4	4	4

The number 10 in the 1^st row and 4^th column tells us that if the space available to us is only 4 units and we take only 1 table of Baccarat, then the utility will be 10. The last two rows in each table tell us the number of tables taken (d₁) to get the maximum utility (F₁) for each column (i.e. space available). For example, the number 21 tells us that if we have 13 units of space available then taking 3 tables of Baccarat, instead of one or two, gives us the maximum utility of 21.

STAGE 2: Game: Blackjack Space occupied per table: 5 units Utility Values: 9, 9, 8, 8.

d\S	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
0	0	0	0	0	10	10	10	10	17	17	17	17	21	21	21	21	22	22	22	22	22	22	22	22	22	22
1	¾	¾	¾	¾	¾	9	9	9	9	19	19	19	19	26	26	26	26	30	30	30	30	31	31	31	31	31
2	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	18	18	18	18	28	28	28	28	35	35	35	35	39	39	39	39
3	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	26	26	26	26	36	36	36	36	43	43	43
4	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	34	34	34	34	44	44
F₂	0	0	0	0	10	10	10	10	17	19	19	19	21	26	28	28	28	30	35	36	36	36	39	43	44	44
d₂	0	0	0	0	0	0	0	0	0	1	1	1	0	1	2	2	2	1	2	3	3	3	2	3	4	4

At stage two, Baccarat and Blackjack are considered together. The number 19 (in row 1 and column 10) is the utility when 1 Blackjack table (of utility 9) is taken and the space available is 10 units. The Blackjack table takes 5 units of space. This leaves us a space of 5 units for Baccarat tables. From the previous table F₁(5) gives a utility of 10.

This gives us a total utility of 9 + 10 = 19 by taking 1 Blackjack and 1 Baccarat table.

STAGE 3: Game: Roulette Space occupied per table: 6 units Utility Values: 11, 11, 9, 8.

d\S	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
0	0	0	0	0	10	10	10	10	17	19	19	19	21	26	28	28	28	30	35	36	36	36	39	43	44	44
1	¾	¾	¾	¾	¾	¾	11	11	11	11	21	21	21	21	28	30	30	30	32	37	39	39	39	41	46	47
2	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	22	22	22	22	32	32	32	32	39	41	41	41	43	48
3	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	31	31	31	31	41	41	41	41
4	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	¾	39	39
F₃	0	0	0	0	10	10	11	11	17	19	21	21	22	26	28	30	32	32	35	37	39	41	41	43	46	48
d₃	0	0	0	0	0	0	1	1	0	0	1	1	2	0	0,1	1	2	2	0	1	1,2	2	2,3	0	1	2