задача о рюкзаке (классика)

Итак, я должен решить задачу о рюкзаке для класса. Пока что я придумал следующее. Мои компараторы - это функции, которые определяют, какой из двух предметов будет лучшим вариантом (путем просмотра соответствующих кортежей (значение, работа)).

Я решил перебрать возможные предметы с помощью работы меньше, чем maxWork, и, чтобы найти, какой предмет является лучшим вариантом на любом конкретном этапе, я сравнил свой последний предмет со всеми другими предметами, которые мы еще не использовали.

def greedyAdvisor(subjects, maxWork, comparator):
    """
    Returns a dictionary mapping subject name to (value, work) which includes
    subjects selected by the algorithm, such that the total work of subjects in
    the dictionary is not greater than maxWork.  The subjects are chosen using
    a greedy algorithm.  The subjects dictionary should not be mutated.

    subjects: dictionary mapping subject name to (value, work)
    maxWork: int >= 0
    comparator: function taking two tuples and returning a bool
    returns: dictionary mapping subject name to (value, work)
    """

    optimal = {}
    while maxWork > 0:
        new_subjects = dict((k,v) for k,v in subjects.items() if v[1] < maxWork)
        key_list = new_subjects.keys()
        for name in new_subjects:
            #create a truncated dictionary
            new_subjects = dict((name, new_subjects.get(name)) for name in key_list)
            key_list.remove(name)
            #compare over the entire dictionary
            if reduce(comparator,new_subjects.values())==True:
                #insert this name into the optimal dictionary
                optimal[name] = new_subjects[name]
                #update maxWork
                maxWork = maxWork - subjects[name][1]
                #and restart the while loop with maxWork updated
                break
    return optimal

Проблема в том, что я не знаю, почему это неправильно. Я получаю ошибки, и я понятия не имею, где мой код неправильный (даже после добавления операторов печати). Помощь будет очень признательна, спасибо!


python knapsack-problem
person Glassjawed    schedule 15.04.2011    source источник
comment
Вы пытаетесь решить это приблизительно или точно? Потому что использование простого жадного алгоритма решит ее только приблизительно и без каких-либо гарантий качества по сравнению с оптимальным.   -  person Nicholas Mancuso    schedule 16.04.2011
comment
Как вы тестируете / запускаете эту функцию? Пожалуйста, добавьте еще код.   -  person Hamish Grubijan    schedule 16.04.2011
comment
Я только пытаюсь решить это приблизительно.   -  person Glassjawed    schedule 16.04.2011

Ответы (2)


arrow_upward
4
arrow_downward

Использование простого жадного алгоритма не дает никаких ограничений на качество решения по сравнению с OPT.

Вот полностью полиномиальное время (1 - эпсилон) * псевдокод приближения OPT для рюкзака:

items = [...]  # items
profit = {...} # this needs to be the profit for each item
sizes = {...}  # this needs to be the sizes of each item
epsilon = 0.1  # you can adjust this to be arbitrarily small
P = max(items) # maximum profit of the list of items
K = (epsilon * P) / float(len(items))
for item in items:
    profit[item] = math.floor(profit[item] / K)
return _most_prof_set(items, sizes, profit, P)

Теперь нам нужно определить наиболее выгодный алгоритм набора. Мы можем сделать это с помощью динамического программирования. Но сначала давайте пройдемся по некоторым определениям.

Если P - самый прибыльный предмет в наборе, а n - количество предметов, которые у нас есть, то nP, очевидно, является тривиальной верхней границей допустимой прибыли. Для каждого i в {1, ..., n} и p в {1, ..., nP} мы позволяем Sip обозначать подмножество элементов, общая прибыль которых ровно p и общий размер сводится к минимуму. Затем пусть A (i, p) обозначает размер множества Sip (бесконечность, если она не существует). Легко показать, что A (1, p) известно для всех значений p в {1, ..., nP}. Мы определим рекуррентность для вычисления A (i, p), которую мы будем использовать в качестве задачи динамического программирования, чтобы получить приближенное решение.

A(i + 1, p) = min {A(i,p), size(item at i + 1 position) + A(i, p - profit(item at i + 1 position))} if profit(item at i + 1) < p otherwise A(i,p)

Наконец, мы даем _most_prof_set

def _most_prof_set(items, sizes, profit, P):
    A = {...}
    for i in range(len(items) - 1):
        item = items[i+1]
        oitem = items[i]
        for p in [P * k for k in range(1,i+1)]:
            if profit[item] < p:
                A[(item,p)] = min([A[(oitem,p)], \
                                     sizes[item] + A[(item, p - profit[item])]])
            else:
                A[(item,p)] = A[(oitem,p)] if (oitem,p) in A else sys.maxint
    return max(A)

Источник

person Nicholas Mancuso    schedule 15.04.2011

arrow_upward

arrow_downward

person    schedule
comment
этот код рюкзака представляет собой рекурсивный жадный подход. где я сначала располагаю веса в порядке убывания их цен, а затем применяю алгоритм рекурсии для получения результата. - person kamran shaik; 27.05.2017