2차원 배열, 첫 번째 항목의 합을 구하고, 두 번째 항목의 합의 최대값을 구합니다.

다음과 같은 배열이 있습니다

<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()출력 결과: