請教一個套餐問題的算法，大家?guī)臀铱纯脆?/a>

duanjigang

實際應(yīng)用中有這樣一個場景，我抽象成 “套餐問題”，大家?guī)臀蚁胂�，怎樣寫一個算法：

規(guī)則介紹：

(1) 餐廳從農(nóng)民那里收購水果，收購的單位為 “一筐”，每筐水果中包含水果的標準為 35個西瓜和200個蘋果。
(2) 這些標準套餐的水果裝筐運輸?shù)讲蛷d后，要拼成套餐賣給各個客戶，每個套餐由不同個數(shù)的西瓜和蘋果組成，比如套餐A需要3個西瓜和10個蘋果。
(3) 要求：每個套餐只能從同一個筐子中拿出來西瓜和蘋果，這樣方便結(jié)算。
(4) 目前支持的套餐有   c1:2個西瓜4個蘋果 c2: 4個習(xí)慣8個蘋果  c3:4個西瓜16個蘋果, c4 8個西瓜20個蘋果。
由于西瓜價錢比較高，因此，在挑選套餐時，如果c1到c4同時出現(xiàn)，以西瓜個數(shù)多，其次是蘋果個數(shù)多的套餐為優(yōu)先，選擇水果。

問題:
假設(shè)現(xiàn)在有 m 筐水果，要提供 n 份套餐，其中c1,c2,c3,c4套餐的比例為1:2:3:4,請?zhí)峁┮粋�方法，在滿足套餐優(yōu)先級的情況下，挑選盡可能多份數(shù)的套餐。

謝謝！好幾年不搞算法，實在想不出來，只能發(fā)帖求助大家了。
:wink:

cokeboL

版大，表示看不懂題啊。。。

m、n是參數(shù)嗎？c1、c2、c3、c4比例是份數(shù)的比例嗎？如果是，n有了不就能算出份數(shù)了？

挑選盡可能多的份數(shù)是說要根據(jù)m來算出n的最大值嗎？

Susake_

感覺描述有問題
假設(shè)現(xiàn)在有 m 筐水果，要提供 n 份套餐，其中c1,c2,c3,c4套餐的比例為1:2:3:4,請?zhí)峁┮粋�方法，在滿足套餐優(yōu)先級的情況下，挑選盡可能多份數(shù)的套餐。
不是提供n份套餐？這是答案？

duanjigang

cokeboL 發(fā)表于 2014-06-24 16:15
版大，表示看不懂題啊。。。

m、n是參數(shù)嗎？c1、c2、c3、c4比例是份數(shù)的比例嗎？如果是，n有了不就能算出 ...

m是輸入的參數(shù)，n是理想值，求一個最大的值。對，c1:c2:c3:c4就是份數(shù)的比例。希望也能盡可能接近這個比例。

duanjigang

回復(fù) 3# Susake_
  n 為一個最大值，需要輸出呢。


   

cokeboL

瞎分析下，只適用于題目這幾個比例和數(shù)字

1）看下比例，套餐的蘋果西瓜比最大的是4倍，每筐35西瓜200蘋果是200/35大于4，所以這題跟蘋果無關(guān)
2）c1 c2 c3 c4為1:2:3:4，西瓜個數(shù)分別為2:4:4:8，所以c2、c3相當于同一套餐都是西瓜為4個，合并為c23，則 c1:c23:c4為1:5:4
3）c3西瓜8個為c23的2倍，35個西瓜最多分4份c4或8份c23，無論怎么取c4或者c23的組合都與在不同筐里取是一樣，既取一個C4就少2取2個c23，但是任意一筐剩余的3個都可以填充一份c1
     而且一筐最多4份c4加一份c1，按照c1:c23:c4為1:5:4，則無論怎么取c4和c23，都可以忽略c1的影響
4）上一條說了取一個c4相當于少取2個c23，隨便哪個筐取都一樣效果，則需要計算m筐最多能取出多少c23和c4并且 c23:c4=5:4
     因為c1:c4=1:4，如果c4份數(shù)不是4的整數(shù)倍，c1份數(shù)將出現(xiàn)小數(shù)，不行，所以c4必須為4的整數(shù)倍，既c4的份數(shù)剛好為整數(shù)筐來取
5）一筐c4對應(yīng)5份c23既20個蘋果，每筐最多8份c23既一筐c4對應(yīng)5/8筐c23
maxC4Num = 0
for(i=math.floor((float)m/9*4); i<m; i++)
{
        if(i+0.625*(m-i) <= m)
        {
                maxC4Num = i
        }
        else
        {
                break
        }
}

c1Num = maxC4Num
c2Num = maxC4Num*2
c3Num = maxC4Num*3
c4Num = maxC4Num*4

沒有檢查是否正確

cokeboL

看上去像負載均衡似的，版大把具體應(yīng)用場景、特征再詳細描述下？