다음과 같은 배열이 있습니다
<code>items = [[1,10], [3,15], [4,12], [2,9], [3, 17] ....] </code>
항목에서 항목 4개를 꺼내고, 항목[0]의 합이 10이 되도록 요구하고, 항목[1]의 합의 최대값을 구합니다.
최적의 솔루션이 있나요?
다음과 같은 배열이 있습니다
<code>items = [[1,10], [3,15], [4,12], [2,9], [3, 17] ....] </code>
항목에서 항목 4개를 꺼내고, 항목[0]의 합이 10이 되도록 요구하고, 항목[1]의 합의 최대값을 구합니다.
최적의 솔루션이 있나요?
아이디어가 배낭 문제에 붙어 있어서 코드가 나오네요bug
, 즉 수량 4
은 만족하지만 합은 10
이고 실제 상황은 <=10
이 만족되지 않습니다. >...
원래 답변:
이 문제는 배낭 문제인 것 같지만 사실은 배낭의 조건보다 더 까다로운 문제입니다.
각 item
의 두 숫자는 각각 배낭 문제의 weight(重量)
, value(价值)
에 해당할 수 있지만, 배낭 문제와의 차이점은
그래서 저는 전통적인 동적 프로그래밍과 그리디 알고리즘에 해당하는 솔루션을 생각해 내지 못했습니다. 여기서는 그리디 아이디어를 활용한 알고리즘을 제시하지만 다릅니다.1. 여러
item
중에서4
만 선택할 수 있습니다. 즉,4
아이템만 배낭에 넣을 수 있습니다.
2. 총 중량은10
보다 작거나 같아야 합니다.10
1.글쎄요, 솔직히 저는 이 코드에 자신이 없습니다을
items
의 크기에 맞게 내림차순으로 배열합니다.item[1]
2.
을 탐색하여 얻은items
의 합을 계산합니다.item[0]
,10
보다 크면continue
조각을 꺼낼 때까지 최종 결과result
를 추가합니다. .4
[최적의 솔루션을 보장할 수 없습니다] 단지 아이디어일 뿐이므로 다른 전문가들의 의견을 묻고 싶습니다. . ^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>
다음 내용은 위 내용에 따라 변경되었으나 정확하다는 보장은 없습니다. . .
# 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()
출력 결과: