php - 给定一个数组元素，对其元素进行求和，取出在某个区间中出现最大的值

Question

这个题呢已经用Python实现了，想改写成PHP代码，卡在了对元素不重复组合上，求给个思路～

也就是说，有N个元素，也许A+B等于100，而求的是满足结果不超过120的最大组合，正好A+C+D等于191。

# -*- 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)

Answer 1

你这题是要考算法的吧

rets = list(itertools.combinations(loop, i))

直接这样穷举必然不适合啊,数据量大一点必然会挂, 这应该算是个背包的问题, 具体描述可以看

背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

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

如果要php里itertools的功能可以看这个

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