Optimal Internet shopping

A naive brute force approach would be to try all possible ways we could have bought the books. That would take $O(\text{shopCount}^\text{bookCount})$ time.

We can do slightly better, i.e, in time $O(2^{\text{shopCount}} \cdot\text{bookCount}\cdot \text{shopCount})$ .

Our plan is to first generate the set of shops from which we are going to order. Once this set is known, we can tell that the delivery charge is going to be the number of shops in the set, times the delivery charge for each shop. And, once the set of shops is fixed, we can find the best possible shop from which we can buy this book simply by iterating over all the shops in the set.

In pseudocode:

1
2
3

Guess which set of shops to order from.
For each book in the list of books,
  guess which shop in the guessed set sells it the cheapest

Of course, a deterministic machine cannot guess, which means we have to iterate over all possible subsets of shops. To do this in a compact way, we use a $\text{shopCount}$ -bit integer to represent a subset of the shops. We use some bit manipulation hacks to manipulate this sets.

First, we have the data:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

bookCount = 10
shopCount = 10
deliveryCharge = 4


cost = [[13, 19, 16, 19, 19, 18, 17, 16, 15, 14],
        [18, 13, 17, 14, 15, 16, 15, 17, 18, 17],
        [17, 14, 13, 17, 16, 18, 16, 17, 18, 17],
        [19, 18, 17, 13, 16, 15, 15, 16, 17, 14],
        [16, 14, 17, 18, 13, 16, 15, 16, 17, 16],
        [17, 17, 16, 14, 15, 13, 16, 17, 18, 16],
        [17, 14, 16, 17, 15, 16, 13, 18, 19, 17],
        [17, 16, 15, 14, 17, 16, 15, 13, 15, 15],
        [15, 15, 16, 18, 17, 15, 16, 15, 13, 14],
        [16, 14, 16, 18, 17, 17, 15, 16, 18, 13]]

And a function to count the number of elements in a set index

1
2
3
4
5
6

def countSetBits(x):
    bits = 0
    while x:
            bits += 1
            x &= x-1
    return bits

And finally, the main program:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

bestCostSoFar = float('inf')
bestSourcesSoFar = [None for i in range(bookCount)] #from where should you buy the books

for setIndex in range(1, 1 << shopCount): # iterate over all possible subsets -- excluding the empty set
    totalDeliveryCharge = deliveryCharge * countSetBits(setIndex)
    costForThisSet = 0
    bookSourcesForThisSet = [None for i in range(bookCount)]
    costForThisSet += totalDeliveryCharge
    for bookId in range(bookCount):
        minBookCost = float('inf')
        for shopId in range(shopCount): #find out which shop in our set sells this book for the cheapest price
            if (1 << shopId) & setIndex: #if this particular shop is in the set we are considering
                if cost[bookId][shopId] < minBookCost:
                    bookSourcesForThisSet[bookId] = shopId
                    minBookCost = cost[bookId][shopId]
        costForThisSet += minBookCost
    if costForThisSet < bestCostSoFar:
        bestCostSoFar = costForThisSet
        bestSourcesSoFar = bookSourcesForThisSet

To get the result,

1
2

print(bestCostSoFar)
print(bestSourcesSoFar)

The full code is here

Each book is on sale for $ $13$ in exactly one store, and each store sells exactly one book for $ $13$ . Thus the smallest theoretical amount that could be spent, if $k$ shops are used, is $ $(13k + 14(10-k) + 4k) =$ $ $140 + 3k$ , presuming that it is possible to buy a book for $ $13$ at each of the $k$ stores, and all other books for $ $14$ .

It is possible to do this with $k=3$ stores, buying Maths, French, Art and Biology from Store 2, History, Geography and Physics from Store 4 and English, Chemistry and Music from Store 10. We cannot better this price by using $3$ or more stores.

The best price that can, in fact, achieved using just $1$ store is $ $157$ (buying all books from either Store 7 or Store 10), so our only chance of improving on $ $149$ is to use $2$ stores. We can in fact spend $ $149$ in $2$ stores, buying Maths, French, Art and Biology from Store 2 and all the other books from Store 10 (we spend $ $4$ more on the book prices, but save the $ $4$ delivery charge). This price of $ $149$ is achieved with 2 books at $ $13$ , 6 books at $ $14$ , 1 book at $ $15$ and 1 book at $ $16$ , plus $ $8$ delivery charges. This price of $ $149$ is only $ $3$ above the theoretical $2$ -store minimum, and simple inspection shows that it is not possible to improve on this profile of book costs (to improve on this score, no book costing $ $17$ or more could be bought, and at most one book for $ $16$ would be allowed). Thus the minimum cost is $ $\boxed{149}$ .

Observe, that because of delivery costs only few shops should be choosen with 3-4 books from each. Shops with books costing 13 or 14 should be taken into account. These are Shop 2, Shop 4 and Shop 10 with books costing 137, but adding delivery costs we have 149 in total.