请教一个套餐问题的算法，大家帮我看看噢

duanjigang

实际应用中有这样一个场景，我抽象成 “套餐问题”，大家帮我想想，怎样写一个算法：

规则介绍：

(1) 餐厅从农民那里收购水果，收购的单位为 “一筐”，每筐水果中包含水果的标准为 35个西瓜和200个苹果。
(2) 这些标准套餐的水果装筐运输到餐厅后，要拼成套餐卖给各个客户，每个套餐由不同个数的西瓜和苹果组成，比如套餐A需要3个西瓜和10个苹果。
(3) 要求：每个套餐只能从同一个筐子中拿出来西瓜和苹果，这样方便结算。
(4) 目前支持的套餐有   c1:2个西瓜4个苹果 c2: 4个习惯8个苹果  c3:4个西瓜16个苹果, c4 8个西瓜20个苹果。
由于西瓜价钱比较高，因此，在挑选套餐时，如果c1到c4同时出现，以西瓜个数多，其次是苹果个数多的套餐为优先，选择水果。

问题:
假设现在有 m 筐水果，要提供 n 份套餐，其中c1,c2,c3,c4套餐的比例为1:2:3:4,请提供一个方法，在满足套餐优先级的情况下，挑选尽可能多份数的套餐。

谢谢！好几年不搞算法，实在想不出来，只能发帖求助大家了。
:wink:

cokeboL

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

m、n是参数吗？c1、c2、c3、c4比例是份数的比例吗？如果是，n有了不就能算出份数了？

挑选尽可能多的份数是说要根据m来算出n的最大值吗？

Susake_

感觉描述有问题
假设现在有 m 筐水果，要提供 n 份套餐，其中c1,c2,c3,c4套餐的比例为1:2:3:4,请提供一个方法，在满足套餐优先级的情况下，挑选尽可能多份数的套餐。
不是提供n份套餐？这是答案？

duanjigang

cokeboL 发表于 2014-06-24 16:15
版大，表示看不懂题啊。。。

m、n是参数吗？c1、c2、c3、c4比例是份数的比例吗？如果是，n有了不就能算出 ...

m是输入的参数，n是理想值，求一个最大的值。对，c1:c2:c3:c4就是份数的比例。希望也能尽可能接近这个比例。

duanjigang

回复 3# Susake_
  n 为一个最大值，需要输出呢。


   

cokeboL

瞎分析下，只适用于题目这几个比例和数字

1）看下比例，套餐的苹果西瓜比最大的是4倍，每筐35西瓜200苹果是200/35大于4，所以这题跟苹果无关
2）c1 c2 c3 c4为1:2:3:4，西瓜个数分别为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份数不是4的整数倍，c1份数将出现小数，不行，所以c4必须为4的整数倍，既c4的份数刚好为整数筐来取
5）一筐c4对应5份c23既20个苹果，每筐最多8份c23既一筐c4对应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

看上去像负载均衡似的，版大把具体应用场景、特征再详细描述下？