女朋友的单位需要解一个背包问题,说白了就是算票。通过有限的票,凑出最接近一个数字的组合来。

这个是经典问题,不过票数比较多,我本来用随机划分,然后一次优化一步的随机算法,凑出一个接近的数字。这样算法比较快,不过不是很准。

女朋友领导发话了,时间长点可以接受,但是最好准点。

照做吧,幸好这个算法算100张票子也就是10秒不到,这还是mini-itx。

下面上算法,具体算法猛击这里(http://www.oiers.cn/pack/Index.html )和这里(http://zh.wikipedia.org/wiki/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98 )。输入是数字列表和目标,输出是组合和误差。f[i]是目前为止,最大代价为i所能获得的最高收益,以及组合方式。numlist是二维数组,分别是代价和收益。

def resolv_dym(numlist, target):
	f = [[0, []] for i in range(0, target + 1)]
	for c, w in numlist:
		for v in range(target, c - 1, -1):
			if f[v - c][0] + w > f[v][0]:
				f[v][0] = f[v - c][0] + w
				f[v][1] = f[v - c][1] + [(c, w), ]
	return f[target][1], float(abs(target - f[target][0]))

当然,在这个特例里面,代价和收益相等,所以下面是真实代码。

def resolv_dym(numlist, target):
	f = [[0, []] for i in range(0, target + 1)]
	for i in numlist:
		for v in range(target, i - 1, -1):
			if f[v - i][0] + i > f[v][0]:
				f[v][0] = f[v - i][0] + i
				f[v][1] = f[v - i][1] + [i, ]
	return f[target][1], float(abs(target - f[target][0]))

完毕。