有如下數組
<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>