二维数组,首项和确定,求第二项和的最大值
程序员文章站
2022-04-29 22:04:20
...
有如下数组
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.9
def 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-8
def 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 result
func()
输出结果:
[[2, 8], [2, 9], [3, 15], [3, 17]]