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

WBOY
發布: 2016-08-10 09:07:18
原創
1092 人瀏覽過

有如下數組

<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]的和,若大於10continue,否則添加斤最終結果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>
登入後複製
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網:公益線上PHP培訓,幫助PHP學習者快速成長!