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