考虑以下问题陈述:
给定一个由n个整数组成的列表,w = {w1,w2,…,wn},另一个整数W表示期望的总和。从“ w”中选择零个或多个数字,以使这些数字的总和尽可能接近但不超过预期的总和(W)。
“ w”的每个元素可以选择多次。see code:
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”进行多个选择的无限制条件感到麻烦。请帮忙!
最佳答案
如果可以多次选择每个元素,则不再是背包问题(即NP难题),可以应用Bézout's identity,可以通过使用extended euclidean algorithm解决。
或者你可以解决诸如此类的问题
return max (KnapSack(i+1, w, X, W), KnapSack(i, w, X-w[i], W))