Home > Backend Development > PHP Tutorial > Two-dimensional array, the sum of the first item is determined, find the maximum value of the sum of the second item

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

WBOY
Release: 2016-08-10 09:07:18
Original
1115 people have browsed it

There is the following array

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

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>
Copy after login
Copy after login

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>
Copy after login

Output result:

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

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>
Copy after login
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template