首頁 > 後端開發 > php教程 > 給定一個陣列元素,將其元素求和,取出在某個區間中出現最大的值

給定一個陣列元素,將其元素求和,取出在某個區間中出現最大的值

WBOY
發布: 2016-09-30 09:37:33
原創
1214 人瀏覽過

這個題呢已經用Python實現了,想改寫成PHP代碼,卡在了對元素不重複組合上,求給個思路~

B等於100,而求的是滿足結果不超過120的最大組合,正好A+C+ <div class="code" style="position:relative; padding:0px; margin:0px;"><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">&lt;code class=&quot;python&quot;&gt;# -*- 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 &lt;= 5000 and s &gt; m: # 求和值 m = s # 组合的列表 m_list = ret # 最大值 print(m) # 求和的元素 print(m_list) &lt;/code&gt;</pre><div class="contentsignin">登入後複製</div></div><div class="contentsignin">登入後複製</div></div> 回覆內容:

這個題呢已經用Python實現了,想改寫成PHP代碼,卡在了對元素不重複組合上,求給個思路~

B

等於100,而求的是滿足結果不超過

120

的最大組合,正好

A+C+ <div class="code" style="position:relative; padding:0px; margin:0px;"><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">&lt;code class=&quot;python&quot;&gt;# -*- 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 &lt;= 5000 and s &gt; m: # 求和值 m = s # 组合的列表 m_list = ret # 最大值 print(m) # 求和的元素 print(m_list) &lt;/code&gt;</pre><div class="contentsignin">登入後複製</div></div><div class="contentsignin">登入後複製</div></div> 你這題是要考算法的吧

<code>rets = list(itertools.combinations(loop, i))</code>
登入後複製
直接這樣窮舉必然不適合啊,數據量大一點必然會掛, 這應該算是個背包的問題, 具體描述可以看 背包問題(Knapsack problem)是一種組合最佳化的NP完全問題。問題可以描述為:給定一組物品,每種物品都有自己的重量和價格,在限定的總重量內,我們如何選擇,才能使得物品的總價格最高。問題的名稱來自於如何選擇最合適的物品放置於給定背包中。

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

如果要php裡itertools的功能可以看這個

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

相關標籤:
php
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板