# 二维数组，首项和确定，求第二项和的最大值

• 2.8k

``````items = [[1,10], [3,15], [4,12], [2,9], [3, 17] ....]
``````

3 个回答

1.众多`item`只能选`4`个，即背包里只能装`4`个物品。
2.总重量严格要求等于`10`，而非小于等于`10`

1.将`items`按照`item[1]`的大小降序排列。
2.遍历`items`，并计算取得的`item[0]`的和，若大于`10``continue`，否则添加斤最终结果`result`中，直到取出`4`个。

``````# 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 < 1 or total < 1:
break
print result

func()``````

``[[3, 17], [3, 15], [1, 10], [2, 9]]``

A : 1 3 5 7
B : 2 3 4 7

`1+3+5+7 > 2+3+4+7`=>`1+5 > 2+4`

``````# 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:
return []

if count == 1:
return findMaxItem(sum,items)

while len(items) > 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]]``

``````#include<iostream>
#include <cstdlib>

using namespace std;

struct item
{
int k,v;
}items[9]={{1,10},{3,15},{4,12},{2,9},{3,17},{5,1},{7,22},{2,8},{4,6}};

int a[3][11];
int ans;
int main()
{
ios::sync_with_stdio(false);

for(int i(0); i != 9; ++i)
{
if(items[i].k < 11 && a[2][10 - items[i].k] && a[2][10 - items[i].k] + items[i].v > ans)
{
ans = a[2][10 - items[i].k] + items[i].v;
}
for(int j(1); j > -1; --j)
{
for(int k(10 - items[i].k); k > -1; k--)
{
if(a[j][k] && a[j + 1][k + items[i].k] < a[j][k] + items[i].v)
{
a[j + 1][k + items[i].k] = a[j][k] + items[i].v;
}
}
}
if(a[0][items[i].k] < items[i].v)
{
a[0][items[i].k] = items[i].v;
}
}

cout << ans << endl;

return EXIT_SUCCESS;
}
``````

###### 你尚未登录，登录后可以
• 和开发者交流问题的细节
• 关注并接收问题和回答的更新提醒
• 参与内容的编辑和改进，让解决方法与时俱进