Задача о ранце, с фиксированным выбором (обязательно) - PullRequest
Новая
       75

Задача о ранце, с фиксированным выбором (обязательно)

0 голосов
/ 21 февраля 2020

Я новичок в python и работаю над некоторыми проблемами в книге. Прямо сейчас я реализовал код (вначале создавая класс et c) для оптимизации комбинации заданных элементов. Теперь я хотел бы поставить некоторые требования, например, в комбинации должен быть либо Project 1 или Project 2. Другой пример будет, если Project 1 включает также для добавления Project 2. Я пытался изменить код ниже функции fastMaxVal, но не сделал удалось решить проблему.

Я надеюсь, что кто-нибудь подскажет мне, что мне нужно изменить. Это было бы очень полезно и спасибо заранее.

С уважением, 


class Item(object): # return object which is choosen
    def __init__(self, n, v, w):
        self.name = n 
        self.value = v
        self.weight = w
    def getName(self):
        return self.name
    def getValue(self):
        return self.value
    def getWeight(self):
        return self.weight
    def __str__(self):
        result = '< ' + self.name + '  PV: ' + str(self.value) + ', Weight of investment: $'\
        + str(self.weight) + ' >'
        return result

def value(item): #for the value 
    return item.getValue()

def weightInverse(item): #weight inverse as said in the name
    return 1.0/item.getWeight()

def density(item):
    return item.getValue()/item.getWeight()

#toConsider(items that are higher in the tree)
#avail = available
#memo = memorized (kepp track of possibilities it has already evaluated)
def fastMaxVal(toConsider, avail, memo = {}):
    if (len(toConsider), avail) in memo:
        result = memo[(len(toConsider), avail)]
    elif toConsider == [] or avail == 0:
        result = (0, ())
    elif toConsider[0].getWeight() > avail:
        result = fastMaxVal(toConsider[1:], avail, memo)
    else:
        nextItem = toConsider[0]
        withVal, withToTake = fastMaxVal(toConsider[1:], avail - nextItem.getWeight(), memo)
        withVal += nextItem.getValue()
        withoutVal, withoutToTake = fastMaxVal(toConsider[1:], avail, memo)
        if withVal > withoutVal:
            result = (withVal, withToTake + (nextItem,))
        else:
            result = (withoutVal, withoutToTake)
    memo[(len(toConsider), avail)] = result
    return result

def smallTest():
    names = ['Project 1', 'Project 2', 'Project 3', 'Project 4', 'Project 5', 'Project 6', 
             'Project 7', 'Project 8', 'Project 9', 'Project 10']
    vals = [NPV_1, NPV_2, NPV_3, NPV_4, NPV_5, NPV_5, NPV_7, NPV_8, NPV_9, NPV_10]
    weights = [-inv_1[0], -inv_2[0], -inv_3[0], -inv_4[0], -inv_5[0], -inv_6[0], -inv_7[0], 
               -inv_8[0], -inv_9[0], -inv_10[0]]
    Items = []
    for i in range(len(vals)):
        Items.append(Item(names[i], vals[i], weights[i]))
    val, taken = fastMaxVal(Items, 100000)
    for item in taken:
        print(item)
    print('Total PV of investments taken = $', round(val, 2))
...