Python 中的无界背包

Question

考虑以下问题陈述：

给定一个包含 n 个整数的列表，w={w1,w2,…,wn}，以及另一个整数，W 代表预期的总和。 Select 来自 '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 space 个分隔的整数组成，w1,w2,…,wn，代表列表 w.

的元素

我在允许从 'w' 中进行多项选择的无限制条件方面确实遇到了麻烦。请帮忙！

Answer 1

如果每个元素都可以选择多次，这就不再是背包问题（即NP hard），可以应用Bézout's identity that can be solved applying extended euclidean algorithm。

或者你可以只修复

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

Python 中的无界背包

Unbounded Knapsack in Python

python

knapsack-problem