二維數組，首項和確定，求第二項和的最大值

有如下數組

<code>items = [[1,10], [3,15], [4,12], [2,9], [3, 17] ....]
</code>

從items中取出4個，要求item[0]和為10，求item[1]和的最大值。

有無最優解？

回覆內容：

有如下數組

<code>items = [[1,10], [3,15], [4,12], [2,9], [3, 17] ....]
</code>

從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中，直到取出個

呃，不過說實話，我對自己這段程式碼

【沒有信心，不能保證最優解】，只是一個思路，所以還請其他諸位大神多提提意見。 ^0^

以下是代碼：

<code># 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()</code>

輸出結果：

<code>[[3, 17], [3, 15], [1, 10], [2, 9]]</code>

依照樓上改了以下，不保證正確。 。 。

<code># 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()</code>

輸出結果：

<code>[[2, 8], [2, 9], [3, 15], [3, 17]]</code>