寻找贪婪背包问题的最优子集（python）

Question

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

Answer 1

你贪婪的方法在很多情况下会失败。

一个这样微不足道的案例：

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

在这种情况下，您的算法将选择（第1项）sum=5，但最佳答案应该是（第2项和第3项）sum=7。

# 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)