免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2692 | 回复: 6

[算法] 请教一个套餐问题的算法,大家帮我看看噢 [复制链接]

论坛徽章:
0
发表于 2014-06-24 14:43 |显示全部楼层
实际应用中有这样一个场景,我抽象成 “套餐问题”,大家帮我想想,怎样写一个算法:

规则介绍:

(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:


论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2014-06-24 16:15 |显示全部楼层
版大,表示看不懂题啊。。。

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

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

论坛徽章:
11
巨蟹座
日期:2013-12-23 11:12:14双子座
日期:2014-08-28 09:14:55子鼠
日期:2014-07-25 16:21:22摩羯座
日期:2014-07-23 15:17:47摩羯座
日期:2014-05-30 13:09:05午马
日期:2014-04-30 18:10:00天秤座
日期:2014-04-25 12:12:00申猴
日期:2014-04-22 11:30:15午马
日期:2014-03-07 16:06:40辰龙
日期:2013-12-25 18:36:00摩羯座
日期:2014-09-02 17:00:55
发表于 2014-06-24 16:26 |显示全部楼层
感觉描述有问题
假设现在有 m 筐水果,要提供 n 份套餐,其中c1,c2,c3,c4套餐的比例为1:2:3:4,请提供一个方法,在满足套餐优先级的情况下,挑选尽可能多份数的套餐。
不是提供n份套餐?这是答案?

论坛徽章:
0
发表于 2014-06-24 16:26 |显示全部楼层
本帖最后由 duanjigang 于 2014-06-24 16:27 编辑
cokeboL 发表于 2014-06-24 16:15
版大,表示看不懂题啊。。。

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

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

论坛徽章:
0
发表于 2014-06-24 16:27 |显示全部楼层
回复 3# Susake_
  n 为一个最大值,需要输出呢。


   

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2014-06-24 18:06 |显示全部楼层
本帖最后由 cokeboL 于 2014-06-24 21:02 编辑

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

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

没有检查是否正确

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2014-06-25 09:44 |显示全部楼层
看上去像负载均衡似的,版大把具体应用场景、特征再详细描述下?
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会,7折限时优惠重磅来袭!
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。

限时七折期:2019年8月31日前


----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP