有如下数组
items = [[1,10], [3,15], [4,12], [2,9], [3, 17] ....]

从items中取出4个，要求item[0]和为10，求item[1]和的最大值。
有无最优解？
回复内容： 有如下数组
items = [[1,10], [3,15], [4,12], [2,9], [3, 17] ....]

从items中取出4个，要求item[0]和为10，求item[1]和的最大值。
有无最优解？
由于思路停留在背包问题，代码确实出现了bug，即数量4满足，但总和为10并没有满足，实际情况是……
原答案：
这个问题看似是个背包问题，实则比背包的条件更加苛刻。
每个item的两个数可以分别对应背包问题里的weight（重量）和value（价值），但与背包不同的是：
1.众多item只能选4个，即背包里只能装4个物品。
2.总重量严格要求等于10，而非小于等于10。
所以传统的动态规划和贪心算法我暂时没能想到对应的解法，我这里给出一段算法，借鉴了贪心的思路，但有所不同：
1.将items按照item[1]的大小降序排列。
2.遍历items，并计算取得的item[0]的和，若大于10，continue，否则添加斤最终结果result中，直到取出4个。
呃，不过说实话，我对自己这段代码【没有信心，不能保证最优解】，只是一个思路，所以还请其他诸位大神多提提意见。^0^
以下是代码：
# coding=utf-8# python2.7.9def func(): items = [[1,10], [3,15], [4,12], [2,9], [3, 17], [5, 1], [7, 22], [2, 8], [4, 6]] # 按照item[1]降序排列 items = sorted(items, key=lambda item: item[1], reverse=true) result = [] # 总和 total = 10 # 总数 count = 4 for item in items: # item[0]的最大取值 limit = total - count if item[0] > limit: continue result.append(item) total = total - item[0] count = 4 - len(result) if count
输出结果：
[[3, 17], [3, 15], [1, 10], [2, 9]]
按照楼上改了以下，不保证正确。。。
# coding=utf-8def func(): items = [[1,10], [3,15], [4,12], [2,9], [3, 17], [5, 1], [7, 22], [2, 8], [4, 6]] # 按照item[1]降序排列 items = sorted(items, key=lambda item: item[1]) print(findmaxitems(10,items,4))def findmaxitems(sum,items,count): if sum 0: item = items.pop() left_items = findmaxitems(sum - item[0],items[:],count - 1) if len(left_items) == (count - 1): left_items.append(item) return left_items return []def findmaxitem(value,items): max = none; for item in items: if item[0] == value: if max == none or item[1] > max[1]: max = item if max == none: result = [] else: result = [max] return resultfunc()
输出结果：
[[2, 8], [2, 9], [3, 15], [3, 17]]