虽然我以前的答复介绍了polytime近似算法对这个问题，要求被
专门_为一个实现方式制成Pisinger的polytime动态规划的解决方案时，所有的_X 我_在 _X 是积极的：
from bisect import bisectdef balsub(X,c): """ Simple impl. of Pisinger's generalization of KP for subset sum problems satisfying xi >= 0, for all xi in X. Returns the state array "st", which may be used to determine if an optimal solution exists to this subproblem of SSP. """ if not X: return False X = sorted(X) n = len(X) b = bisect(X,c) r = X[-1] w_sum = sum(X[:b]) stm1 = {} st = {} for u in range(c-r+1,c+1): stm1[u] = 0 for u in range(c+1,c+r+1): stm1[u] = 1 stm1[w_sum] = b for t in range(b,n+1): for u in range(c-r+1,c+r+1): st[u] = stm1[u] for u in range(c-r+1,c+1): u_tick = u + X[t-1] st[u_tick] = max(st[u_tick],stm1[u]) for u in reversed(range(c+1,c+X[t-1]+1)): for j in reversed(range(stm1[u],st[u])): u_tick = u - X[j-1] st[u_tick] = max(st[u_tick],j) return st哇，真令人头疼。这需要进行校对，因为在实现的同时
balsub，我无法定义正确的比较器来确定是否存在针对此SSP子问题的最佳解决方案。
