>백엔드 개발 >PHP 튜토리얼 >2차원 배열, 첫 번째 항목의 합을 구하고, 두 번째 항목의 합의 최대값을 구합니다.

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

WBOY
WBOY원래의
2016-08-10 09:07:181119검색

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

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

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.