使用迭代加深DFS解决背包类似问题

Question

我正在解决类似背包的问题：即打印出 objects 的第一个组合，其值高于数字但重量低于限制。

我试过：

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

我知道这棵树是这样的

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

谢谢！！

Answer 1

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

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)

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

使用迭代加深DFS解决背包类似问题

Using Iterative deepening DFS for knapsack similar problem

knapsack-problem

depth-first-search

iterative-deepening