Given an array element, sum its elements and get the largest value in a certain interval.

This question has been implemented in Python. I want to rewrite it into PHP code, but I am stuck on the non-repeated combination of elements. Please give me some ideas~

In other words, there are N elements, maybe A+B is equal to 100, and what we are looking for is the maximum combination that satisfies the result of not exceeding 120, which happens to be A+C+D is equal to 191 .

<code class="python"># -*- coding=UTF-8 -*-

import itertools

loop = [509, 838, 924, 650, 604, 793, 564,
        651, 697, 649, 747, 787, 701, 605, 644]

m = 0
m_list = []
for i in range(0, len(loop)):
    # 目的是打乱其排序，找出任意种可能
    rets = list(itertools.combinations(loop, i))
    for ret in rets:
      # 将循环器中的元组求和
        s = sum(ret)
        if s <= 5000 and s > m:
            # 求和值
            m = s
            # 组合的列表
            m_list = ret

# 最大值
print(m)
# 求和的元素
print(m_list)
</code>

Reply content:

This question has been implemented in Python. I want to rewrite it into PHP code, but I am stuck on the non-repeated combination of elements. Please give me some ideas~

In other words, there are N elements, maybe A+B is equal to 100, and what we are looking for is the maximum combination that satisfies the result of not exceeding 120, which happens to be A+C+D is equal to 191 .

<code class="python"># -*- coding=UTF-8 -*-

import itertools

loop = [509, 838, 924, 650, 604, 793, 564,
        651, 697, 649, 747, 787, 701, 605, 644]

m = 0
m_list = []
for i in range(0, len(loop)):
    # 目的是打乱其排序，找出任意种可能
    rets = list(itertools.combinations(loop, i))
    for ret in rets:
      # 将循环器中的元组求和
        s = sum(ret)
        if s <= 5000 and s > m:
            # 求和值
            m = s
            # 组合的列表
            m_list = ret

# 最大值
print(m)
# 求和的元素
print(m_list)
</code>

Your question is about algorithm, right?

<code>rets = list(itertools.combinations(loop, i))</code>

It’s definitely not suitable to exhaustively do this directly. If the amount of data is larger, it will inevitably fail. This should be regarded as a backpack problem. You can see the detailed description

The Knapsack problem is an NP-complete problem of combinatorial optimization. The problem can be described as: given a set of items, each item has its own weight and price, within the limited total weight, how do we choose so that the total price of the items is the highest. The name of the problem comes from how to choose the most appropriate item to place in a given backpack.

https://zh.wikipedia.org/wiki...

If you want the function of itertools in php, you can read this

https://github.com/alts/iter.php