Two-dimensional array, the sum of the first item is determined, find the maximum value of the sum of the second item

There is the following array

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

Take out 4 items from items, require the sum of item[0] to be 10, and find the maximum value of the sum of item[1].

Is there an optimal solution?

Reply content:

There is the following array

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

Take out 4 items from items, require the sum of item[0] to be 10, and find the maximum value of the sum of item[1].

Is there an optimal solution?

Because the idea is stuck on the backpack problem, a bug does appear in the code, that is, the quantity 4 is satisfied, but the total is 10, which is not satisfied. The actual situation is <=10...

---

Original answer:

This problem seems to be a backpack problem, but in fact it is more demanding than the conditions of a backpack.

The two numbers of each item can respectively correspond to the weight (weight) and value (value) in the knapsack problem, but the difference from the knapsack problem is:

1. There are many item and you can only choose 4, that is, the backpack can only hold 4 items.
2. The total weight is strictly required to be equal to 10, not less than or equal to 10.

So I haven’t been able to think of the corresponding solutions for the traditional dynamic programming and greedy algorithms. Here I give an algorithm that draws on the greedy idea, but it is different:

1. Arrange items in descending order according to the size of item[1].
2. Traverse items and calculate the sum of the obtained item[0]. If it is greater than 10, continue, otherwise add pounds to the final result result until 4 are taken out.

Well, to be honest, I have no confidence in this code of mine[cannot guarantee the optimal solution]. It is just an idea, so I would like to ask other experts to give their opinions. ^0^

Here is the 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>

Output result:

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

The following has been changed according to the above, but it is not guaranteed to be correct. . .

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