Phone Numbers as Possible Combinations of 7 digits: Probability

1.) If the first digit isn't allowed to be a 0 or a 1, how many 7-digit phone numbers are possible?

Solution: For each digit in the phone number, there are 10 possibilities (0 - 9) if there are no restrictions. In this case the first number isn't allowed to be 0 or 1. For phone-number digits 2 - 7, there are $10^{6}$ possibilities: 10 * 10 * 10 * 10 * 10 * 10. Multiply this by the number of possibilities for the first digit (only 8 since two digits, 1 and 0, are excluded), and you get your answer:

No. of possibilities for the first digit * No. of possibilities for the remaining 6 digits

= $8*10^{6}$ = 8,000,000 possible phone numbers.

2.) If the above condition stays in place, along with the added condition that the first three digits of the phone number cannot be 911, how many possible phone numbers are there?

Solution: If the probability of an event A occurring is P(A), then the probability of event A not occurring is 1 - P(A). Consider the case where the event A is the choosing of the first three digits of the phone number to be 911:

The probability space of the first three digits is $8*10*10$ if we consider only the condition of part 1. The probability of the first three digits being 911 is $\frac{1}{8}*\frac{1}{10}*{\frac{1}{10}} = \frac{1}{800}$

So, the probability of the first three digits not being 911 is $ 1 -\frac{1}{800} = \frac{799}{800}$

Finally, the number of possible phone numbers with the first digit not being a 0 or a 1, and the first 3 digits not being 911, is
$799 * 10^{4} $ = 7,990,000.

(799 is the number of possibilities for the first 3 digits, and $10^{4}$ is the number of possibilities for the last 4 digits.)

0-1 Knapsack Problem: Dynamic Programming

In a previous post, we covered a brute-force solution to the knapsack problem. This time we'll make our solution more efficient by using dynamic programming, where we break the original problem down in to smaller sub-problems. If we do this, we can keep the results of the sub-problems stored in an array and just grab them from the cells they occupy as we need them rather than recomputing them.

Consider, intuitively, some sub-problems of the whisky-thief problem we tackled last time. We said our knapsack capacity was 10 bottles (weight = 10). If we consider a different knapsack problem where our knapsack capacity is 2 bottles and we only have two bottles to consider, we can take everything, meaning the two bottles under consideration. This individual case would be like considering a knapsack filled with other bottles and having a remaining capacity of 2; our options are the same. Likewise, if we had a knapsack already filled to capacity, this would be like having a knapsack of zero capacity (like not having a knapsack at all, really); we just couldn't take any bottles in this case. Consider the following array:

V	W		0	1	2	3	4	5	6	7	8	9	10
0	0	0	0
360	2	1
360	3	2
310	1	3
320	4	4
300	2	5

The cell (0, 0) represents the case where we have a knapsack capacity of zero, and no item to be considered. The columns 0 - 10 represent knapsacks of various carrying capacities, 0 being the lowest and 10 being the highest. The rows 0 - 5 represent the items (Scotch whiskies) under consideration. 0 meaning no items to be considered, and 5 meaning the case where we consider all five whiskies. The last cell in the bottom-right corner represents the original knapsack problem that we wish to optimize here. V is the value of an item and W is the weight of the item under consideration. The array we're actually filling in here doesn't include the row with the varying knapsack capacities or the column with the various whisky-item numbers.

V	W		0	1	2	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	0	0	0	0	0
360	2	1
360	3	2
310	1	3
320	4	4
300	2	5

The cell (0, 1) highlighted above represents the case of a knapsack with a capacity of 1, and no whiskies under consideration (item = 0). You can easily guess that it will be 0.

V	W		0	1	2	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	0	0	0	0	0
360	2	1	0	0	360	360	360	360	360	360	360	360	360
360	3	2
310	1	3
320	4	4
300	2	5

When we get to cell (1, 2), we consider the case of a knapsack with a carrying capacity of 2, and item 1, which has an item weight of 2. This means we can take it. And, if we do, we have no more room available in this knapsack, which doesn't matter because we have only considered one item so far. From here, it doesn't matter how large we make the knapsack, we'll only ever consider the one item, so each cell gets the same value filled in. The values in the cells represent the total value of the items in the hypothetical knapsacks. Moving on...

V	W		0	1	2	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	0	0	0	0	0
360	2	1	0	0	360	360	360	360	360	360	360	360	360
360	3	2	0	0	360	360	360	720	720	720	720	720	720
310	1	3	0	310	360	670	670	720	1030	1030	1030	1030	1030
320	4	4	0	310	360	670	670	720	1030	1030	1030	1040	1350
300	2	5	0	310	360	670	670	970	1030	1030	1330	1330	1350

In the above array, consider cell (2, 2). Here, the items under consideration are item 1 (Macallan 18) and item 2 (Lagavulin 12). In this case, our knapsack capacity is 2, and item 2 weighs 3, so it can't fit. However, we know already that item 1 will fit, so we include it and enter 360 into the cell. We just dragged the value of the cell directly above it down into it. We repeat the process until we consider a knapsack of capacity 5. Now we can insert the Lagavulin (item 2) as well. Or leave it, if we so desire. But, why do that? If we do that, our total value in the knapsack will be the value of item one, which is 360. Compare that to the total value we would get if we took the Lavavulin, which would be 360 + 360 = 720, and we see we'd be foolish not to take it. So we do. We repeat the process until we get to the last cell, and there we see our maximum profit if we take the right combination of whiskies. What that combination is we'll determine later. For now, let's try to make an algorithm that gives us the above solution for the maximum value ($1350)

We'll call our array k[i][w], with i rows and w columns, representing the item numbers and the weights of the knapsacks respectively. Let the weights of the items (in terms of bottles, remember) be given in the list weights = [0, 2, 3, 1, 4, 2], and their values be given in the list values = [0, 360, 360, 310, 320, 300].

for i in range(len(item)):
    for w in range(C + 1):
     1.   if i == 0 or w == 0:    #case with no bottles or no knapsack (base case)
              k[i][w] = 0
    
     2.   elif weights[i] > w: 
              k[i][w] = ks[i-1][w]     #item weight exceeds capacity of knapsack (w)
     3.   else:
            p1 = ks[i-1][w]    #case where we don't take ith whisky
            p2 = values[i] + k[i-1][w - weights[i])    #case where we take ith whisky
            k[i][w] = max(p1, p2)    #considers which case gives max profit
return k[i][w]

1. This step in the algorithm should be self-explanatory.
2. Look again at our array above at cell (1, 1). Here, we consider the case of a knapsack with carrying capacity 1 (w = 1), and an item with weight 2. In our algorithm, this would be weights[i] = 2, and w = 1. So, since the weight of the item is greater than the knapsack carrying capacity, k[1][1] = 0, which is k[1-1][1]. We've just dragged the value from the cell in the row above (0, 1) down into the cell we're working on (1, 1). Now, look at cell (2, 2), which corresponds to the consideration of item 2, which has a weight of 3 (weights[i] = 3). In this case, the knapsack capacity is w = 2; weights[i] > w, so we drag the value of the cell in the row above down into (2, 2). Or, as our algorithm performs the move, k[2][2] = k[1][2].
3. Now, take a look at cell (2, 5). Here we make a comparison. The carrying capacity of the knapsack is w = 5, and the weight of the item is item[2] = 3. We calculate p1 = k[1][5] = 360. We could just drag that value down into cell (2, 5) and be done with it, but we shouldn't. We need to calculate the value of p2, the total profit of the knapsack items if we were to take item 2 as well as item 1. This gives us p1 = values[2] + k[1][5 - weights[2]] = 360 + 360 = 720. p1 = value of item 2 + value of item 1. Notice that k[1][5 - weights[2]] = k[1][2], which is the value from the cell where we first stored the value of item 1. 

Now, for the combination of items that gives us our max value of $1350. Compare the last two cells at the ends of the rows corresponding to items 4 and 5 (Now, we are considering a knapsack with a carrying capacity of w = 10 bottles).

They both have a value of 1350, so not taking item 5 has no impact on our profit. Leave it out. Now compare the last two cells at the ends of the rows corresponding to items 3 and 4. Including item 4 seems to give a greater value, so we definitely take it. Our remaining capacity is now 10 - 4 = 6. Items 5 and 4 are no longer under consideration (we've taken item 4 and left out item 5), so now we compare values for items 3 and 2. Look at cells (3, 6) and (2, 6). The items under consideration are 3 and 2, with a remaining knapsack capacity w = 6.

  

 Here, we clearly want to take item 3 (total value = 1030). We can repeat the process until we get to 

i = 0 and w = 0.

The algorithm goes: (Recall C was the chosen knapsack capacity, in this case 10)

take = []

i = len(item) - 1

w = C

while i > 0 and w > 0:

    q1 = k[i][w]

    q2 = k[i - 1][w] 

    if q1 <= q2:

        i -= 1

        continue

    else:

        take.append(items[i])

        i -= 1

        w -= weights[i]

The complete code (in Python):

       

Don't forget to import numpy.

I used the following inputs to test the function:

whiskies = ['None','Macallan 18', 'Lagavulin 12', 'Springbank 21',  'Ballantines 21', 'Johnnie Walker Blue']
weight = [0,2,3,1,4,2]
value = [0,360,360,310,320,300]

print(ks(whiskies, weight, value, 10))