Zweidimensionales Array: Bestimmen Sie die Summe des ersten Elements und ermitteln Sie den Maximalwert der Summe des zweiten Elements

Es gibt das folgende Array

<code>items = [[1,10], [3,15], [4,12], [2,9], [3, 17] ....]
</code>

Nehmen Sie 4 Elemente aus den Elementen heraus, setzen Sie voraus, dass die Summe von Element[0] 10 beträgt, und ermitteln Sie den Maximalwert der Summe von Element[1].

Gibt es eine optimale Lösung?

Antwortinhalt:

Es gibt das folgende Array

<code>items = [[1,10], [3,15], [4,12], [2,9], [3, 17] ....]
</code>

Nehmen Sie 4 Elemente aus den Elementen heraus, setzen Sie voraus, dass die Summe von Element[0] 10 beträgt, und ermitteln Sie den Maximalwert der Summe von Element[1].

Gibt es eine optimale Lösung?

Da die Idee beim Rucksackproblem hängen bleibt, erscheint der Code bug, das heißt, die Menge 4 ist erfüllt, aber die Summe ist 10 und ist nicht erfüllt. Die tatsächliche Situation ist <=10...

---

Ursprüngliche Antwort:

Dieses Problem scheint ein Rucksackproblem zu sein, aber tatsächlich ist es anspruchsvoller als die Bedingungen eines Rucksacks.

Die beiden Zahlen von jedem item können jeweils weight（重量） und value（价值） im Rucksackproblem entsprechen, aber der Unterschied zum Rucksackproblem ist:

1. Es kann nur item aus mehreren 4s ausgewählt werden, d. h. der Rucksack kann nur 4 Artikel enthalten.
2. Das Gesamtgewicht muss unbedingt 10 und nicht kleiner oder gleich 10 sein.

Daher konnte ich mir keine entsprechenden Lösungen für die traditionelle dynamische Programmierung und die Greedy-Algorithmen vorstellen. Hier stelle ich einen Algorithmus vor, der auf der Greedy-Idee basiert, aber anders ist:

1. Ordnen Sie items in absteigender Reihenfolge nach der Größe von item[1] an.
2. Durchlaufen Sie items und berechnen Sie die Summe der erhaltenen item[0]s. Wenn sie größer als 10 ist, continue, addieren Sie andernfalls das Endergebnis result, bis 4 Stücke herausgenommen werden .

Nun, um ehrlich zu sein, habe ich kein Vertrauen in meinen Code [kann die optimale Lösung nicht garantieren] Es ist nur eine Idee, daher möchte ich andere Experten um ihre Meinung bitten. ^0^

Hier ist der Code:

<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>

Ausgabeergebnis:

<code>[[3, 17], [3, 15], [1, 10], [2, 9]]</code>

Das Folgende wurde entsprechend den oben genannten Änderungen geändert, es kann jedoch nicht garantiert werden, dass es korrekt ist. . .

<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>
</p>
<p>Ausgabeergebnis: </p>
<pre class="brush:php;toolbar:false"><code>[[2, 8], [2, 9], [3, 15], [3, 17]]</code>