Попытка найти оптимальное подмножество для задачи Жадного ранца (python) - PullRequest
Новая
       73

Попытка найти оптимальное подмножество для задачи Жадного ранца (python)

0 голосов
/ 04 мая 2020

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

Это были мои указания: реализовать жадный алгоритм, который упорядочивает элементы в порядке убывания значения к весу (vi / wi для i = 1, 2, ..., n ), затем выбирайте элементы в этом порядке, пока вес следующего элемента не превысит оставшуюся емкость (Примечание: в этой жадной версии мы останавливаемся сразу после первого элемента, включение которого превысит емкость ранца). 

def greedy_knapsack(val, weight, W, n):
    # index = [0, 1, 2, ..., n - 1] for n items
    index = list(range(len(val)))
    # contains ratios of values to weight
    ratio = [v / w for v, w in zip(val, weight)]
    QuickSort(ratio, 0, len(ratio) - 1)
    max_value = 0
    for i in index:
        if weight[i] <= W:
            max_value += val[i]
            W -= weight[i]
        else:
            max_value += val[i] * W // weight[i]
            break
    return max_value

1 Ответ

0 голосов
/ 04 мая 2020

Ваш жадный подход во многих случаях потерпит неудачу.

Один из таких тривиальных случаев: 

weight = [10, 10, 10]
value = [5, 4, 3]
W = 7

В этом случае ваш алгоритм выберет (элемент 1) sum = 5, но оптимальный ответ должен быть (пункты 2 и 3), сумма = 7.

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

# Prints the items which are put in a  
# knapsack of capacity W 
def printknapSack(W, wt, val, n): 
    K = [[0 for w in range(W + 1)] 
            for i in range(n + 1)] 

    # Build table K[][] in bottom 
    # up manner 
    for i in range(n + 1): 
        for w in range(W + 1): 
            if i == 0 or w == 0: 
                K[i][w] = 0
            elif wt[i - 1] <= w: 
                K[i][w] = max(val[i - 1]  
                  + K[i - 1][w - wt[i - 1]], 
                               K[i - 1][w]) 
            else: 
                K[i][w] = K[i - 1][w] 

    # stores the result of Knapsack 
    res = K[n][W] 
    print(res) 

    w = W 
    for i in range(n, 0, -1): 
        if res <= 0: 
            break
        # either the result comes from the 
        # top (K[i-1][w]) or from (val[i-1] 
        # + K[i-1] [w-wt[i-1]]) as in Knapsack 
        # table. If it comes from the latter 
        # one/ it means the item is included. 
        if res == K[i - 1][w]: 
            continue
        else: 

            # This item is included. 
            print(wt[i - 1]) 

            # Since this weight is included 
            # its value is deducted 
            res = res - val[i - 1] 
            w = w - wt[i - 1] 

# Driver code 
val = [ 60, 100, 120 ] 
wt = [ 10, 20, 30 ] 
W = 50
n = len(val) 

printknapSack(W, wt, val, n)

ref: https://www.geeksforgeeks.org/printing-items-01-knapsack/

...