游客:
注册
|
登录
会员
|
搜索
|
统计
|
帮助
轩辕春秋文化论坛
»
设计与修改
» 一个简单的算法题
兴唐传·瓦岗山异闻录(20150519版)发布
(2015-5-19)
论坛营运现状公告
(2014-8-10)
三国志12pk版下载
(2013-4-20)
《精忠报国岳飞传》制作组对外开放
(2013-1-16)
岳飞传解密剧本发布
(2011-4-12)
招募各版斑竹和网站管理技术人员
(2006-4-19)
<< 上一主题
|
下一主题 >>
投票
交易
悬赏
活动
打印
|
推荐
|
订阅
|
收藏
|
开通个人空间
|
加入资讯
标题: 一个简单的算法题
Maxwell
代王
监管使
枢密直学士
山南西道节度使
★
组别
诸侯
级别
征东将军
好贴
4
功绩
1845
帖子
5801
编号
622
注册
2004-7-7
#1
发表于 2010-11-28 15:02
资料
文集
短消息
看全部作者
一个简单的算法题
有n件商品,价格分别为:
v1, v2, v3, v4, ..., vn
有现金m元,求解是否可以从n件商品中选择若干件价格正好为m元。
求所有符合要求的组合,并输出每种组合中若干件商品的序号,若无符合要求的组合,输出无解。
注:价格v和m都是浮点数,n <=28
---------------------------------------------
当初选择n < 60太过随意了,测试了一下自己的代码,选择了一个时间可以接受的值n <= 28
[
本帖最后由 Maxwell 于 2010-11-30 00:00 编辑
]
[广告]
安装Alexa工具条,提高轩辕排名,支持轩辕发展!
Maxwell
代王
监管使
枢密直学士
山南西道节度使
★
组别
诸侯
级别
征东将军
好贴
4
功绩
1845
帖子
5801
编号
622
注册
2004-7-7
#2
发表于 2010-11-29 23:37
资料
文集
短消息
看全部作者
QUOTE:
原帖由
zhaohaidao
于 2010-11-29 00:01 发表
标记下,尝试用下贪心算法。。
贪心算法可以考虑,不过就是可能无法找到所有解。
[广告]
《精忠报国岳飞传完整版》火热发布
Maxwell
代王
监管使
枢密直学士
山南西道节度使
★
组别
诸侯
级别
征东将军
好贴
4
功绩
1845
帖子
5801
编号
622
注册
2004-7-7
#3
发表于 2010-11-30 00:01
资料
文集
短消息
看全部作者
QUOTE:
原帖由
周瑜
于 2010-11-29 23:53 发表
我用递归法把程序写出来了,可惜复杂度太高,对于 n=60 无能为力。
目前改为n <= 28了,其实没有仔细算过n应该取多少合适,你自己选择一个上限也没问题
[广告]
《精忠报国岳飞传完整版》火热发布
Maxwell
代王
监管使
枢密直学士
山南西道节度使
★
组别
诸侯
级别
征东将军
好贴
4
功绩
1845
帖子
5801
编号
622
注册
2004-7-7
#4
发表于 2010-11-30 22:46
资料
文集
短消息
看全部作者
QUOTE:
原帖由
周瑜
于 2010-11-30 00:18 发表
由于 vi 和 m 都是浮点数,因此也就断绝了我使用动态规划的想法。
上述代码可能的优化包括:
1.先对 candidates 数组进行降序排列,这样前几步更容易得到超过 target 值的和,假设所有价格均为正数,则立即 ...
如果用分做vi和m的单位,那就是整数了。
还可以做一些优化,不过不会有数量级上的变化了。28是我测试了穷举法能够在1分钟内执行完的一个值,看起来是给小了。
[广告]
《精忠报国岳飞传完整版》火热发布
Maxwell
代王
监管使
枢密直学士
山南西道节度使
★
组别
诸侯
级别
征东将军
好贴
4
功绩
1845
帖子
5801
编号
622
注册
2004-7-7
#5
发表于 2010-11-30 22:48
资料
文集
短消息
看全部作者
QUOTE:
原帖由
阿尔法孝直
于 2010-11-30 12:11 发表
我觉得题目表达有点奇怪:
按照出题的原意,似乎应该是:
有n种商品,单价分别为:
v1, v2, v3, v4, ..., vn
有现金m元,求解是否可以从n种商品中,每种选择若干件,总价正好为m元。
不过现在的题 ...
何谓出题原意?
[广告]
真诚支持说岳,携手共创辉煌
投票
交易
悬赏
活动
正在浏览此帖的会员 - 共
1
人在线
轩辕春秋文化论坛
轩辕史话
> 炎黄春秋
> 我思我在
> 法律探讨
> 三国史话
春秋文艺
> 古典小说
> 诗词歌赋
> 现代文艺
> 韦编三绝
> 对联雅座
> 滴翠亭
> 藏经阁
> 双七钟社
> 笑书神侠
> 辕门射虎
> 虎帐点兵
游戏人生
> 同人战棋手游
> 三国戏英杰传
> 三国鼎立
> 轩辕公会
> 三国志12
> 英雄史诗
> 运筹帷幄
> 人间五十年
> 步步为营
> 游行天下
> 游戏贴图
轩辕工作室
> 兴唐传·瓦岗山异闻录
> 豪华曹操传
> 精忠报国岳飞传
> 《精忠报国岳飞传》制作组
> 大一统演义
> 曹操传MOD作品交流
> 东吴霸王传
> 封神英杰传
> 杨家将
> 吕布传
> 三国无双战略版
> 北宋志·赵匡胤传
> 战旗春秋
> 曹操传MOD制作交流
> 金庸群侠传MOD交流
> 风华录
> 设计与修改
怡情岁月
> 影音经典
> 动漫先锋
> 绘画摄影
> 情感轩辕
> 衣食住行
> 体坛动力
> 谈股论金
参政议政
> 迎宾阁
> 鸿胪寺
> 登闻鼓
> 监造府
当前时区 GMT+8, 现在时间是 2025-7-25 04:49
京ICP备2023018092号
轩辕春秋
2003-2023 www.xycq.org.cn
Powered by
Discuz!
5.0.0
2001-2006
Comsenz Inc.
Processed in 0.011186 second(s), 9 queries , Gzip enabled
TOP
清除 Cookies
-
联系我们
-
轩辕春秋
-
Archiver
-
WAP
控制面板首页
编辑个人资料
积分交易
公众用户组
好友列表
基本概况
论坛排行
主题排行
发帖排行
积分排行
管理团队
管理统计