search
HomeBackend DevelopmentPHP TutorialTwo-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 ...


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

Output result:

<code>[[2, 8], [2, 9], [3, 15], [3, 17]]</code>
Statement
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
How do you create and use an interface in PHP?How do you create and use an interface in PHP?Apr 30, 2025 pm 03:40 PM

The article explains how to create, implement, and use interfaces in PHP, focusing on their benefits for code organization and maintainability.

What is the difference between crypt() and password_hash()?What is the difference between crypt() and password_hash()?Apr 30, 2025 pm 03:39 PM

The article discusses the differences between crypt() and password_hash() in PHP for password hashing, focusing on their implementation, security, and suitability for modern web applications.

How can you prevent Cross-Site Scripting (XSS) in PHP?How can you prevent Cross-Site Scripting (XSS) in PHP?Apr 30, 2025 pm 03:38 PM

Article discusses preventing Cross-Site Scripting (XSS) in PHP through input validation, output encoding, and using tools like OWASP ESAPI and HTML Purifier.

What is autoloading in PHP?What is autoloading in PHP?Apr 30, 2025 pm 03:37 PM

Autoloading in PHP automatically loads class files when needed, improving performance by reducing memory use and enhancing code organization. Best practices include using PSR-4 and organizing code effectively.

What are PHP streams?What are PHP streams?Apr 30, 2025 pm 03:36 PM

PHP streams unify handling of resources like files, network sockets, and compression formats via a consistent API, abstracting complexity and enhancing code flexibility and efficiency.

What is the maximum size of a file that can be uploaded using PHP ?What is the maximum size of a file that can be uploaded using PHP ?Apr 30, 2025 pm 03:35 PM

The article discusses managing file upload sizes in PHP, focusing on the default limit of 2MB and how to increase it by modifying php.ini settings.

What is Nullable types in PHP ?What is Nullable types in PHP ?Apr 30, 2025 pm 03:34 PM

The article discusses nullable types in PHP, introduced in PHP 7.1, allowing variables or parameters to be either a specified type or null. It highlights benefits like improved readability, type safety, and explicit intent, and explains how to declar

What is the difference between the unset() and unlink() functions ?What is the difference between the unset() and unlink() functions ?Apr 30, 2025 pm 03:33 PM

The article discusses the differences between unset() and unlink() functions in programming, focusing on their purposes and use cases. Unset() removes variables from memory, while unlink() deletes files from the filesystem. Both are crucial for effec

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

SublimeText3 Linux new version

SublimeText3 Linux new version

SublimeText3 Linux latest version

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools