## Algorithms – The 0/1 Knapsack Problem – Dynamic Programming method

Okay, I didn’t see that James had made a video about the very same subject. Great minds think alike I guess? Sigh. Well, here it is: The Dynamic Programming method for solving a 0/1 Knapsack Problem explained, in depth, by me in under 11 minutes!

Bug 1: Ignore the “The cell with the green circle around has a capacity of” blah blah etc. because I uploaded the wrong version ._. The green circle should be around cell (3,1).
Bug 2: I circle item ‘1’ when I should circle item ‘3’ at the end when we’re going through the keep array. I fail.
Bug 3: I say ‘2’ somewhere instead of ‘3’. See if you can spot it.

## Dutch Books

In the previous post we talked about probability theory, and talked about agents having a probability distribution to represent their degrees of belief.  We also talked about the axioms K1 and K2, that is:

K1 – If a is always true, then p(a) = 1.
K2 – If a AND b are never true at the same time, then the probability of a OR b being true is p(a) + p(b).

These axioms become more important when we talk about the idea of a ‘dutch book’.

## Artificial Intelligence

Artificial Intelligence is the field of computer science that concerns itself with getting better and more positive responses to the question ‘Can machines think?’.  Over the years there have been a number of approaches to artificial intelligence, the current best method that is growing in popularity is the use of probability theory in AI, and this probabilistic reasoning is spreading to almost all areas of Artificial Intelligence.

## Relations

If we have two sets, A and B, we can refer to the ‘Cartesian Product’ as being A x B.  This means that if A = {1, 2, 3} and B = {a, b, c}, then A x B = {1a, 1b, 1c, 2a, 2b, 2c, 3a, 3b, 3c}.  It’s the set of all pairs of values where the first is from A and the second  is from B.

A relation from A to B is a subset of A x B.  A relation can be said to connect values together, in a way, showing a relationship between them.

## Patterns

In the last blog post we looked at what the various components in the module, mostly languages, symbols, and alphabets.  Now we’re going to look in more detail at how to define a language from symbols.

To define languages more easily we’re going to look at patterns.  Patterns can also be called regular expressions.  Computers, after all, can’t recognise set notation symbols such as {, }, or ∈.

## Sets & Languages

In order for a computer to organise a textual input, the computer has to be able to recognise certain strings, such as, in parsing a programming language, it has to be able to find ‘if’ or ‘while’.

The first part of Computation deals with how we describe to a computer what string to look for, how to come up with the right description to solve the problem, and how to do more advanced things such as check whether a piece of code is correctly formed, making sure that opening and closing brackets match, or checking that a webpage is written in valid HTML.