Skip to content
Advertisement

Minimal stone piles

Question:
You are given a list of integer weights. You need to distribute these weights into two sets, such that the difference between the total weight of each set is as low as possible.
Input data: A list of the weights.
Output data: A number representing the lowest possible weight difference.

I saw an answer, but I cannot understand why bestval = -1. can anyone help me figure it out? thanks a lot!
code is following:

import itertools;

def checkio(stones):

    total = 0
    for cur in stones:
        total += cur

    bestval = -1

    for i in range(0,len(stones)):
        for comb in itertools.combinations(stones,i):
            weight = 0
            for item in comb:
                weight += item
            d = diff(total - weight, weight)
            if bestval == -1 or d < bestval:
                bestval = d                    
    return bestval

def diff(a,b):
    if a >= b:
        return a - b
    else:
        return b - a

Advertisement

Answer

bestval is just set to -1 initially and is updated the first time around the loop to d. After that, bestval is updated again each time that d is a better value (aka smaller difference in weights) than the current bestval.

The key code is here…

if bestval == -1 or d < bestval:
    bestval = d 

So on the first pass around the loop, bestval == -1 is true, and bestval is updated. After that, the d < bestval check determines whether to update the value.

Advertisement