recursive Knapsack in Python

Navigation
0

I have a list called self.items : 

items = [dict(id=0, w=4, v=12),
             dict(id=1, w=6, v=10),
             dict(id=2, w=5, v=8),
             dict(id=3, w=7, v=11),
             dict(id=4, w=3, v=14),
             dict(id=5, w=1, v=7),
             dict(id=6, w=6, v=9)]

With this, I have to make a list of lists, where each element is combined with the others, including the empty case. The appearance that this list of lists will have at the end will be something like this: 

[[],[{id:0,w:4,v:12}],....,[{id:0,w:4,v:12}, {id:1,w:6,v:10}]....]

Then I have implemented the function brute_force() to find which set of elements has the maximum weight allowed and the maximum value. This is the solution I've found and it's going well: 

 def brute_force(self):
    """ Solves the knapsack problem using brute force
    :return: max_value and list of items
    """
    power_set = self.power_set()
    best_value = 0
    best_set = []
    best_weight = 0

    for p in power_set:
        value=0
        weight=0
        for w in p:
            weight = w['w'] + weight
            value = w['v'] + value
            if weight == self.max_weight:
                best_weight=weight
                if best_value < value:
                    best_value=value
                    best_set=p


    return best_value, best_weight, best_set

Now I must do the same but recursively. This is where I start having problems. I know that the fact of being recursive implies that I do not have to use for because I already do it when I call the function N times, but I do not know how to take what I want from self.items , which is the maximum value. With for yes I would know but without him no.

This is the recursive function of which I speak: 

def recursive(self, n, max_weight):
    """ Recursive Knapsack
    :param n: Number of elements
    :param max_weight: Maximum weight allowed
    :return: max_value
    """
    self.iterations += 1 
    result = 0
    #
    # Add code
    #

    return result

And this is the solution that I have been able to reach after several hours. 

 def recursive(self, n, max_weight):
    """ Recursive Knapsack
    :param n: Number of elements
    :param max_weight: Maximum weight allowed
    :return: max_value
    """
    self.iterations += 1 
    result = 0
    #
    # Add code
    #
    if max_weight > self.max_weight: #they gave me the self.max_weightas a variable of method __init__ which shows me what is the maximum weight permitted
        self.recursive(self, self.items+self.iterations, max_weight)
        if max_weight < self.max_weight:
            self.recursive(self, self.items+self.iterations, max_weight)
        else:
                result = self.items['v']+result

    return result
    
asked by VictorP 08.11.2016 в 23:49
source

1 answer

1

You should change the chip. Python has many facilities to process lists and dictionaries without loops for .

To obtain all possible combinations: 

from itertools import combinations

power_set = sum((list(combinations(items,i))
                for i in range(0,len(items)+1)), [])

In order to work better, we define functions to calculate the weight and value of a set: 

def sum_weigth(p):
    return sum(x["w"] for x in p)

def sum_value(p):
    return sum(x["v"] for x in p)

To select only those that do not exceed one peso: 

power_set_filtered = [p for p in power_set
                         if sum_weigth(p) < max_weigth ]

Once filtered, we are left with the most valuable: 

best_set = max(power_set_filtered, key=sum_value)

Combining everything, it can be simplified more: 

def sum_weigth(p):
    return sum(x["w"] for x in p)

def sum_value(p):
    return sum(x["v"] for x in p)

power_set_filtered = (p for i in range(0, len(items)+1)
                            for p in combinations(items, i) 
                                if sum_weigth(p) < max_weigth )

best_set = max(power_set_filtered, key=sum_value)
    
answered by 09.11.2016 в 10:35
Access images form Obtain the code (primary key) of a combobox