I have been attending several online computer science and algorithm courses and one of the popular examples is the Knapsack problem, which is typically presented when learning Greedy and Dynamic Programming Algorithms. When I learned the Knapsack problem I immediately thought of the popular game Clash of Clans.

There is a well-known trick in Clash of Clans that allows one to hide elixir and dark elixir in barracks by queuing troops in the barracks when the army camps are full. Clash of Clans charges for the troops but one can remove the troops from the barracks later and retrieve the money as a refund. This essentially hides the elixir and dark elixir from attackers by reducing the amount of loot in the base.

This trick is a form of the discrete Knapsack problem that allows for repetitions. Given a barrack that can hold a maximum number of spaces, one wants to maximize the total amount of elixir or dark elixir hidden in the barrack given a set of troops that take a certain number of spaces and are worth a certain amount of money.

For example, I currently have a th7 mini-account that has all level 9 (dragon) barracks. Each barrack can hold 60 spaces. Not all my troops are maxed yet, and so here is a list of the troops I can queue in my barracks.

Troop Spaces Cost
Barbarian 1 60
Archer 1 120
Giant 5 1750
Goblin 1 60
Wall Breaker 2 2000
Balloon 5 3000
Wizard 4 3000
Healer 14 5000
Dragon 20 29000

Although not necessary, if troops have the same number of spaces, I kept only the most valuable one. For example, archer hides more elixir than the barbarian and goblin, and the balloon hides more elixir than the giant. The list of troops can be reduced for better performance.

Troop Spaces Cost
Archer 1 120
Wall Breaker 2 2000
Wizard 4 3000
Balloon 5 3000
Healer 14 5000
Dragon 20 29000

So given these troops, what troop composition will allow me to hide the most elixir in a Level 9 Barrack that holds 60 spaces?

Dynamic Programming

Dynamic Programming using Python seems like a perfect fit for this solution. I first start with a barrack that holds 0 spaces and calculate the best troop configuration and most amount of elixir that I can hide for each barrack up to a total of 60 spaces. Here is the Python Script that I wrote using Dynamic Programming to solve the Knapsack problem.

max_spaces_available_in_barrack = 60

# troops available to place in barracks
# ( name, space used, cost )
# A = Archer, W = Wall Breaker, Z = Wizard
# B = Balloon, H = Healer, D = Dragon
troops = [
    ('A', 1, 120),
    ('W', 2, 2000),
    ('Z', 4, 3000),
    ('B', 5, 3000),
    ('H', 14, 5000),
    ('D', 20, 29000)
]

# initial values when barrack has 0 spaces
total_elixir_hidden = [0]
troop_composition = [[]]

for i in range(1, max_spaces_available_in_barrack + 1):
    current_best_elixir_hidden = -1
    current_best_troop_composition = None

    for troop in troops:
        if (i - troop[1] > -1) and (total_elixir_hidden[i - troop[1]] + troop[2] > current_best_elixir_hidden):
            current_best_elixir_hidden = total_elixir_hidden[i - troop[1]] + troop[2]
            current_best_troop_composition = troop_composition[i - troop[1]] + [troop[0]]

    total_elixir_hidden.append(current_best_elixir_hidden)
    troop_composition.append(current_best_troop_composition)

    print '{0:2} {1:5} - {2}'.format(i, total_elixir_hidden[i], troop_composition[i])

Here is the output of the Python Script.

 1   120 - ['A']
 2  2000 - ['W']
 3  2120 - ['W', 'A']
 4  4000 - ['W', 'W']
 5  4120 - ['W', 'W', 'A']
 6  6000 - ['W', 'W', 'W']
 7  6120 - ['W', 'W', 'W', 'A']
 8  8000 - ['W', 'W', 'W', 'W']
 9  8120 - ['W', 'W', 'W', 'W', 'A']
10 10000 - ['W', 'W', 'W', 'W', 'W']
11 10120 - ['W', 'W', 'W', 'W', 'W', 'A']
12 12000 - ['W', 'W', 'W', 'W', 'W', 'W']
13 12120 - ['W', 'W', 'W', 'W', 'W', 'W', 'A']
14 14000 - ['W', 'W', 'W', 'W', 'W', 'W', 'W']
15 14120 - ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'A']
16 16000 - ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W']
17 16120 - ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'A']
18 18000 - ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W']
19 18120 - ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'A']
20 29000 - ['D']
21 29120 - ['D', 'A']
22 31000 - ['D', 'W']
23 31120 - ['D', 'W', 'A']
24 33000 - ['D', 'W', 'W']
25 33120 - ['D', 'W', 'W', 'A']
26 35000 - ['D', 'W', 'W', 'W']
27 35120 - ['D', 'W', 'W', 'W', 'A']
28 37000 - ['D', 'W', 'W', 'W', 'W']
29 37120 - ['D', 'W', 'W', 'W', 'W', 'A']
30 39000 - ['D', 'W', 'W', 'W', 'W', 'W']
31 39120 - ['D', 'W', 'W', 'W', 'W', 'W', 'A']
32 41000 - ['D', 'W', 'W', 'W', 'W', 'W', 'W']
33 41120 - ['D', 'W', 'W', 'W', 'W', 'W', 'W', 'A']
34 43000 - ['D', 'W', 'W', 'W', 'W', 'W', 'W', 'W']
35 43120 - ['D', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'A']
36 45000 - ['D', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W']
37 45120 - ['D', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'A']
38 47000 - ['D', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W']
39 47120 - ['D', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'A']
40 58000 - ['D', 'D']
41 58120 - ['D', 'D', 'A']
42 60000 - ['D', 'D', 'W']
43 60120 - ['D', 'D', 'W', 'A']
44 62000 - ['D', 'D', 'W', 'W']
45 62120 - ['D', 'D', 'W', 'W', 'A']
46 64000 - ['D', 'D', 'W', 'W', 'W']
47 64120 - ['D', 'D', 'W', 'W', 'W', 'A']
48 66000 - ['D', 'D', 'W', 'W', 'W', 'W']
49 66120 - ['D', 'D', 'W', 'W', 'W', 'W', 'A']
50 68000 - ['D', 'D', 'W', 'W', 'W', 'W', 'W']
51 68120 - ['D', 'D', 'W', 'W', 'W', 'W', 'W', 'A']
52 70000 - ['D', 'D', 'W', 'W', 'W', 'W', 'W', 'W']
53 70120 - ['D', 'D', 'W', 'W', 'W', 'W', 'W', 'W', 'A']
54 72000 - ['D', 'D', 'W', 'W', 'W', 'W', 'W', 'W', 'W']
55 72120 - ['D', 'D', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'A']
56 74000 - ['D', 'D', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W']
57 74120 - ['D', 'D', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'A']
58 76000 - ['D', 'D', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W']
59 76120 - ['D', 'D', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'A']
60 87000 - ['D', 'D', 'D']

Given my current set of troops it appears that I can hide the most elixir in my Level 9 barracks by training 3 dragons, which will hide 87,000 worth of elixir per barrack.

This output appears to make sense if you look at the cost per housing space of each troop. Ideally we want to choose troops that are more valuable per housing space. In this case, dragon and wall breaker offer the highest value per housing space.

Troop Cost / Space
Archer 120
Wall Breaker 1000
Wizard 750
Balloon 600
Healer 357
Dragon 1450

If one tried to solve this Knapsack problem using a Greedy Algorithm in Python, it wouldn't provide an optimal solution.

Kinda cool to solve one of my leisurely activities with a Python Script using Dynamic Programming!

Posted by Koder Dojo

I am a C# ASP.NET MVC Developer learning Python, computer science, algorithms, and cryptography from a variety of online courses. This website is a journal of my adventures and I hope it inspires other developers to learn and share their experience. You can find me on twitter as @KoderDojo.

Related Posts: