试图找到贪婪背包问题的最佳子集（python）

Question

我认为这是找到最佳值的正确算法，但是现在我需要找到使我获得该值的最佳子集。帮助将不胜感激！

这些是我的指示：实施贪婪算法，以值与重量比的降序排列（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

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) 

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