Although the Yellow Turban Army was defeated, the Han Nation was still in a state of chaos under the cruel rule of Dong Zhuo, a powerful warlord who controlled the young Emperor Xian with his unjust commands. A coalition of other warlords, headed by Yuan Shao, declared war against Dong Zhuo, in order to stop his lawlessness. Liu Bei, Guan Yu and Zhang Fei were part of the coalition. The collation army fought against Zhao Yun's army at a place called Yu Lui. But failed many times to defeat Zhao Yun's army. Cao Cao, a member in the collation was familiar with military science and noticed the special formation of Zhao Yun's army. Don's army used Bagua theory to establish their special formation. They formed ten different formations or wall each of which had different Bagua properties. The ten walls were related in such a way that when a wall, for example wall nine was attacked, other walls with the same Bagua properties, walls two and ten with, the wind property, would become unbreakable, and therefore, pointless to attack. For the same reason, if wall five was attacked, then the other five walls that shared the water and earth property would be unbreakable. Now, aware of this strategy, Lui Bei turned to his magical tablet to ask the best way to attack the gates and achieve maximum damage [MUSIC] Liu Bei has to attack Dong Zhuo. Now, he's a master of tactics and he has a very complicated formation which is protected by the magic of the Bagua. So, Liu Bei has ten possible places he can chooses to attack this formation. And these spots are protected by properties of the bagua. Now, each of the spots is backed up by the different sets of properties of the bagua. So we can see here the ten different positions that Liu Bei can attack and which of them is protected by which property of the bagua. But we can think about that another way. So we can think about mapping for each of the Bagua symbols which of the spots they defend. So the magic power of the Bagua is such that if Liu Bei attacks one spot, then all the other spots which are protected by the same any symbol that protects that spot will be reinforced and will not be able to be attacked. So for example, if you attacked spot number 5 which is defended by these two symbols of the Bagua, then spot 6, 8, 10, 1 and 3 which share a symbol. So, 1 and 3 share this symbol and 6, 8, and 10 share the other symbol, then he won't be able to attack those 2 spots. So his problem then, is to decide which of the spots that he should attack. And not all spots are equal in terms of how much damage he can do. So some spots he can do a lot of damage, so spot one and spot ten for example, and other spots, he can do and a little bit of damage. So he has to pick a subset of the spots to attack, at most one spot for each symbol because of course once he attacks one spot for that symbol, all the other spots for that symbol would be magically defended, in order to maximize the damage. So here's our set selection problem. We're given a number of 1 to nSpots, each is associated with a symbol. And we choose a subset of those spots, which includes at most 1 for each of those subsets and maximize the damage points of the chosen set. So for our data here, we've got 10 spots. We've got a damage associated with each of those spots. We've got eight symbols and here's an interesting thing. And many think because it's using Unicode, we can use arbitrary characters here. So these are quite legitimate characters in. And each of these symbols has associated with it a set of spots. And here we've used colors so you can see the association between those symbols in which spots they defend. So if we think about a greedy algorithm for this problem, we can see here's the different spots numbered and then we've connect them together by the symbols that protect them. Now greedy algorithm to tackle this problem would say well choose the spot with the largest damage available and attack that. And then eliminate choices that are no longer valid and then pick the next spot with the largest damage available and keep going. So as it turns out, the first place we can attack with the largest damage is spot number one. But once we do that, we have to eliminate every other spot which shares a symbol. So we have to eliminate, for example, spots four and six, they share that symbol. But we also have to learn all these other spots because they also share a symbol with spot number one. Which only leaves spots 9 and 10 left over and we look at the damage of spots 9 and 10. Spot 10 is also a high damage spot, it requires 10 damage. And then if we eliminate the remaining things we eliminate 9 and there's no more spots and we can see that gives a solution of attacking at spots 1 and 10 with a total damage of 20. Okay let's go back to the model. So we have the number of spots and we're going to generate a set of ints which just determines that set one dot to n spots telling us that range. And with each of those spots we're going to associate a damage, then we have our symbols at the Bagua. And for each of those symbols we have the groups of spots, the set of spots which associated with that symbol. And then here's our decision. Which sets of spots should we attack? And then we have the constraints. So really only one constraint we have is for every symbol, then we can only attack one spot which is associated with that symbol. So we look at the places we attack, the same spots we attack the intersection with the group spots associates with the symbol has to be less or equal to one. So that's the only constraint of the problem, and then, what are we trying to do? Well, we're trying to maximize the total damage. And what is that? Well we just sum up for all the places that we attack, all the spots we attack, the damage. So we're trying to maximize the total damage. So it's a fairly straightforward model. And if we run that model, then, we're going to get a solution, a very different solution from greedy algorithm. We're going to attack spots 4, 5, 7, and 9 for total damage of 21. So, we've done better than greedy algorithm, slightly better but, of course, anything is better for Liu Bei
