与 OPT 相比,使用简单的贪心算法不会对解决方案的质量提供任何限制。
这是背包的完全多项式时间 (1 - epsilon) * OPT 近似伪代码:
items = [...] # items
profit = {...} # this needs to be the profit for each item
sizes = {...} # this needs to be the sizes of each item
epsilon = 0.1 # you can adjust this to be arbitrarily small
P = max(items) # maximum profit of the list of items
K = (epsilon * P) / float(len(items))
for item in items:
profit[item] = math.floor(profit[item] / K)
return _most_prof_set(items, sizes, profit, P)
我们现在需要定义最有利可图的集合算法。我们可以通过一些动态规划来做到这一点。但首先让我们回顾一下一些定义。
如果 P 是集合中利润最高的商品,n 是我们拥有的商品数量,那么 nP 显然是允许利润的一个微不足道的上限。对于 {1,...,n} 中的每个 i 和 {1,...,nP} 中的 p,我们让 Sip 表示总利润为的项目子集exactlyp 且其总大小被最小化。然后我们让 A(i,p) 表示集合 Sip 的大小(如果不存在则无穷大)。我们可以很容易地证明 A(1,p) 对于 {1,...,nP} 中 p 的所有值都是已知的。我们将定义一个递归来计算 A(i,p),我们将其用作动态规划问题,以返回近似解。
A(i + 1, p) = min {A(i,p), size(item at i + 1 position) + A(i, p - profit(item at i + 1 position))} if profit(item at i + 1) < p otherwise A(i,p)
最后我们给出_most_prof_set
def _most_prof_set(items, sizes, profit, P):
A = {...}
for i in range(len(items) - 1):
item = items[i+1]
oitem = items[i]
for p in [P * k for k in range(1,i+1)]:
if profit[item] < p:
A[(item,p)] = min([A[(oitem,p)], \
sizes[item] + A[(item, p - profit[item])]])
else:
A[(item,p)] = A[(oitem,p)] if (oitem,p) in A else sys.maxint
return max(A)
Source https://rads.stackoverflow.com/amzn/click/com/3540653678