python - Python 中的无界背包

Question

考虑以下问题陈述:

给定一个包含 n 个整数的列表，w={w1,w2,…,wn}，以及另一个整数，W 表示预期总和。从“w”中选择零个或多个数字，使这些数字的总和尽可能接近但不超过预期总和 (W)。

• “w”的每个元素都可以被选择多次。

查看代码:


def KnapSack (i, w, X, W):
    if ( w[i:] == [] and X >= 0):
        return  ( W - X )   
    elif ( X < 0 ):
        return 0        
    else:       
        return max (KnapSack(i+1, w, X, W), KnapSack(i+1, w, X-w[i], W))

n, W = raw_input().split()
n, W = [int(n), int(W)]
w = map(int, raw_input().split())
print KnapSack (0, w[0:], W, W)

n 和 W 分别表示列表 w 的长度和期望的总和。第二行由 n 个空格分隔的整数 w1,w2,…,wn 组成，表示列表 w 的元素。

我真的很难处理允许从“w”中进行多项选择的无界条件。请帮忙!

Answer 1

如果每个元素可以被多次选择，这就不再是背包问题(即NP困难)，并且可以应用Bézout's identity可以应用 extended euclidean algorithm 来解决。

或者你可以修复类似的东西

return max (KnapSack(i+1, w, X, W), KnapSack(i, w, X-w[i], W))