The Heist

The Heist, aka Rob to the Big Bank, in Python

[Go to the original problem at Hackerrank]

 

Problem description

The "official" description of this problem was not very clear to me, so I will try to give my own explanation.

Imagine there are N robbers. Each robber can carry up to M (an integer) units of weight, for a combined load capacity of N*M units. They open a vault that contains different types of valuable objects. Each type of object has some unit weight and unit value. You must choose how many items of each type the robbers must take in order to maximize the value.

The following rules apply:

1. The total weight of all items the robbers take must be less than their total load capacity, M*N.
2. The number of items of each type must be an integer, or zero.
3. The vault has an infinite amount of  each object, so the only limiting factor is rule (1).

Mathematical description

Input variables:

• $N,M := \mbox{number of robbers, load capacity per robber}$
• $k := \mbox{different types of items}$
• $Weight_k,Value_k := \mbox{Weight, Value of an item of the k-th type}$

Problem: Find the quantities $Q = \left(q_1,\ldots,q_k\right) \in \mathbb{N}_{0}^{k}, \sum_{i=1}^{i<=k}q_{i}\times Weight_{i}\leq M\times N$ Such that Q maximizes $\sum_{i=1}^{i<=k}q_{i}\times Value_{i}$

Input & output formats

Input

The first line contains N and M, separated by a space.

The following lines contain the definitions for each type of object: Name, unit weight, unit value, separated by commas, without spaces. Note that the original problem statement, available at Hackerrank, is not very clear about this. I used this interpretation as unit weight and value.

The last line contains the word END, in capital letters.

For example:

5 71000
Gold,34500,3000
Bronze,29000,80
Silver,14800,1200
END 

Output

For each item type there should be a line containing the name of the item, the number of items the robbers should take, and the total weight and value of those items the robbers will be taking. Fields should be separated by commas, with no spaces. Items whose quantity is zero should be omitted. The items should be listed in alphabetical order.

Then there should be a line with the total weight and value the robbers will be taking, separated by commas with no spaces.

Finally, there should be a line with the text "Each robber gets: <value>", where <value> should be replaced by the total value divided by the number of robbers, expressed to two decimal digits by rounding.

For example, the output corresponding to the above input is:

Gold,9,310500,27000
Silver,3,44400,3600
354900,30600
Each robber gets: 6120.00 

Solution

 Of course, we could try all possible combinations of items. However, we should expect this approach to time-out as the number of combinations can be very high.

The original problem  statement gives us a clue as to how to solve the problem. It says the when the robbers are considering which items to carry they start by the ones that have a higher value to weight ratio.

In the above example, gold has a value/weight of (3000/34500) = 0.08696, followed by silver with 0.08108 and least valuable is bronze, with 0.00276.

The robbers could then take 10 units of gold, except this would not be an optimal solution. If the took 10 units of gold, each weighting 345000, they would have some remaining load capacity they would be unable to use. If they take one less unit of gold, they can fit 3 units of silver, and 3 silver units are move valuable than 1 gold.

We can now outline our solution.

Outline of the solution

The first approach is as follows:

1. Start by sorting the different types of items according to their value/weight ratio.
2. Then start by calculating how many units you can take of the most valuable (by weigth) item.
3. Subtract the weight of these items from your capacity.
4. Repeat the 2 and 3 with the rest of the items.

This procedure has linear complexity, but does not produce optimal results.

As we mention previously, it is not always the best idea to take all we can of certain item. We should add an additional step, 2b, in which we bifurcate: instead of trying to take only the maximum number of items, we try with all possible values.

This modification gives our algorithm exponential complexity. We are essentially trying an exhaustive search. Of course this will time-out. ¿How can we solve it? We have to accept some sub-optimality and pray that it passes the test cases. In the code below, we try taking from the maximum number of elements, to the maximum number of elements minus 3.

Code

We can define our almost-optimal algorithm recursively:

# The Heist, by Juan I. Carrano | IEEEXtreme 8.0 (2014)
N, M = [int(k) for k in raw_input().split()]

items = {}

while True:
    ss = raw_input().strip()
    if ss == 'END':
        break
    name,sload,sprice = ss.split(',')
    items[name.strip()] = (int(sload), int(sprice))

items_scored = sorted([(float(p)/l, k) for k,(l,p) in items.iteritems()], reverse=True)


def choose(cap_remaining, xitems_scored):
    if not xitems_scored:
        return (0, [])
    else:
        score,item = xitems_scored[0]
        alternatives = []
        l, p = items[item]
        to_load_max = cap_remaining/l

        for to_load in xrange(max(0, to_load_max-3), to_load_max+1):
            this_item = [[item, to_load]]
            this_money = to_load*p

            best_fill_price, best_fill_items = choose(cap_remaining - to_load*l, xitems_scored[1:])

            alternatives.append((this_money + best_fill_price,
                                this_item + best_fill_items))

        return max(alternatives)

total_money, best_solution_items  = choose(N*M, items_scored)

total_weight =0

for it, amount in sorted(best_solution_items):
    l = amount*items[it][0]
    p = amount*items[it][1]
    total_weight += l
    if (amount > 0):
        print "%s,%d,%d,%d"%(it, amount, l, p)

print "%d,%d"%(total_weight, total_money)
print "Each robber gets: %.2f"%(round(100*total_money/float(N))/100.0)

Let's explain  it:

 

Lines 2 to 11

We parse the input. Each type of item is placed in a dictionary (called items) whose keys are the items' names and whose values are tuples of (unit weight, unit value).

 

Line 13:

We create a list with the items sorted from the most valuable to the cheapest, in terms of their price/weight ratio (let's call this the score).

 

Lines 16 to 34, the recursive function choose

This function explores a decision tree in search for the best combination of items. It takes as arguments the capacity available and a list of (item score, item name), sorted so that items with best score come first. It returns the best way to fill up that capacity with the given items, along with the total value of such items.

While it is generally a bad idea to implement a tree search with a recursive function (we are using the program stack as the backtracking stack), it is easier and the problem states that there won't be more than 5 item types, so the recursion depth is limited to a fairly small number.

Let's see how choose works. The terminal case is when there are no items to add. The best and only way to fill up the capacity is to take no items, so we return zero (the price of no items) and an empty list.

If there are items in the xscored_items list we take the first one (the one with the best price/weight ratio) and calculate the maximum amount of units we can take (to_load_max) as the quotient of the capacity divided by the item's unit weight. We then evaluate the possibilities of taking different amounts of units. If this were a completely exhaustive search, we should try taking from 0 to to_load_max and see which one produces the best price. Here we try only with 3 possibilities, greatly reducing the run time at the cost of potential sub-optimality.

The procedure to evaluate a possibility is as follows:

• Line 27: Calculate the price of the units we are taking (to_load*p).
• Line 29: Calculate the weight of the units we are taking (to_load*l). Substract this weight from the current load capacity. Call the function choose with this reduced load capacity and a list of items that excludes the one we are currently evaluating (pass on xitems_scored from the second item onwards). choose should return the best way to fill up the remaining space, and the price of such fill.
• Line 31: The price of the current possibility is the price of the units we are taking plus the price if the best fill up. We also create a list by combining the items returned by choose in line 29 with the possibility we are evaluating.

In line 34 we return the best of all the possibilities we evaluated (the one with the greatest price). This is why we say that choose returns the best way to fill up the available capacity.

 

Lines 38 to 48

This part of the code formats the output according to the requirements of the problem.

 

Files

This code, along with test cases are available at this Drive folder.