The Knapsack Problem

ICMS

Page:

Demo

The number 26 (in row 0 and column 13) is the utility when 13 units of space is available and no Roulette table is taken. If we have 21 units of space and we take only 2 tables of Roulette (with utility = 11+11=22), then 21 (2×6) = 9 units of space is available for Blackjack and Baccarat tables. As F₂(9) = 19, the total utility is 22 + 19 = 41 (in row 2 and column 21).

STAGE 4: Game: Poker Space occupied per table: 3 units Utility Values: 8, 6, 4, 2.

At the last stage, all 4 games are considered and the space available is taken to be maximum (25 units).

S\d	0	1	2	3	4	F₄	d₄
25	48	49	51	50	46	51	2

Thus, the maximum utility of 51 is attained when we take 2 Poker tables.

Optimal policy:

The optimal policy is to set up 2 tables of Poker, 1 table of Roulette, 1 table of Blackjack and 2 tables of Baccarat which gives us a total utility of 51.

Stage	S_n (Space available)	Optimal policy	Transition to space left for previous stage
4	25	d₄ = 2	S₃ = S₄ d₄a₄ = 25 2×3 = 19
3	19	d₃ = 1	S₂ = S₃ d₃a₃ = 19 1×6 = 13
2	13	d₂ = 1	S₁ = S₂ d₂a₂ = 13 1×5 = 80
1	8	d₁ = 2	S₀ = 0

Group Minimisation Algorithm:

In the dynamic programming algorithm, the number of calculations is n × b, where n is the total number of objects and b is the size of the knapsack. In the group minimisation algorithm, use of group theoretic techniques considerably reduces the number of calculations.