1

我正在解决一个类似的背包问题：这是打印出价值高于数字但重量低于限制的对象的第一个组合。

我试过了：

value = [10, 8, 7, 6, 4]
weight = [8, 4, 3, 3, 1]
name = ['A','B','C','D','E']
Wlimit = 8
Vlimit = 8


def ID(maxDepth):
    for i in range(1, maxDepth):
        knapsack = []
        if (DFS(knapsack, 0, 0, i)):
            return True
        else:
            print("cannot find solution")
            return False

def DFS(knapsack, currentValue, currentWeight, maxDepth):
  
    # If reached the maximum depth, stop recursing.
    if maxDepth <= 0 : return False
    if currentValue >= Vlimit and currentWeight <= Wlimit: 
        print(knapsack)
        return True
    
    for i in range(len(name)):
        if name[i] not in knapsack:
            if ((currentWeight + weight[i]) < Wlimit):
                knapsack.append(name[i])
                DFS(knapsack, currentValue + value[i], currentWeight + weight[i], maxDepth - 1)

                knapsack = knapsack[:-1]
                DFS(knapsack, currentValue, currentWeight, maxDepth - 1)
                
            else:
                DFS(knapsack, currentValue, currentWeight, maxDepth - 1)

    return False

我知道这棵树看起来像这样

但我不知道如何用正确的逻辑修复代码希望有人能帮我一把。

谢谢！！

4

1 回答 1

0

我试过这个，它适用于一些样本：

weight = [1,1,3,4,5]
value = [2,1,5,3,5]
name = ['A','B','C','D','E']
knapsack = []
limit_weight = 8
limit_value = 8
n = 5 # number of items

def ID(maxDepth):
    for i in range(maxDepth):
        found, val, arr = DFS(i)
        if found:
            return arr
    return False

def DFS(maxDepth, idx = 0, sum_val = 0, sum_weight = 0, arr = []):
    if maxDepth < 0 : return False, None, None
    if sum_weight > limit_weight : return False, None, None # elements weights exceed knapsack limit
    if sum_val > limit_value : return True, sum_val, arr # elements values greater than required
    if idx >= n : return False, None, None # no more elements and no solution (otherwise we would have returned from the previous line)
    for i in range(idx,n):
        n_arr = arr.copy()
        n_arr.append(name[i])
        found, new_sum_val, new_sum_weight = DFS(maxDepth-1, i+1, sum_val + value[i], sum_weight + weight[i], n_arr)
        if found : return found, new_sum_val, new_sum_weight
    return False, None, None # didn't find a solution

res = ID(4)
print(res)

如果没有找到解决方案，则代码返回 False，如果找到解决方案，则返回元素名称列表。如果您发现任何不清楚的地方，请告诉我。

于 2022-02-28T07:00:00.990 回答