


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 ...
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 choose4
, that is, the backpack can only hold4
items.
2. The total weight is strictly required to be equal to10
, not less than or equal to10
.
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 ofitem[1]
.
2. Traverseitems
and calculate the sum of the obtaineditem[0]
. If it is greater than10
,continue
, otherwise add pounds to the final resultresult
until4
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>

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

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.

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

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.

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.

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.

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

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


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

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

Hot Article

Hot Tools

SublimeText3 Linux new version
SublimeText3 Linux latest version

VSCode Windows 64-bit Download
A free and powerful IDE editor launched by Microsoft

Dreamweaver CS6
Visual web development tools

Dreamweaver Mac version
Visual web development tools

WebStorm Mac version
Useful JavaScript development tools
