标题: 一个简单的算法题
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5801
编号 622
注册 2004-7-7


发表于 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 编辑 ]


顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5801
编号 622
注册 2004-7-7


发表于 2010-11-29 23:37 资料 文集 短消息 看全部作者


QUOTE:
原帖由 zhaohaidao 于 2010-11-29 00:01 发表
标记下,尝试用下贪心算法。。

贪心算法可以考虑,不过就是可能无法找到所有解。


顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5801
编号 622
注册 2004-7-7


发表于 2010-11-30 00:01 资料 文集 短消息 看全部作者


QUOTE:
原帖由 周瑜 于 2010-11-29 23:53 发表
我用递归法把程序写出来了,可惜复杂度太高,对于 n=60 无能为力。

目前改为n <= 28了,其实没有仔细算过n应该取多少合适,你自己选择一个上限也没问题
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5801
编号 622
注册 2004-7-7


发表于 2010-11-30 22:46 资料 文集 短消息 看全部作者


QUOTE:
原帖由 周瑜 于 2010-11-30 00:18 发表
由于 vi 和 m 都是浮点数,因此也就断绝了我使用动态规划的想法。

上述代码可能的优化包括:
1.先对 candidates 数组进行降序排列,这样前几步更容易得到超过 target 值的和,假设所有价格均为正数,则立即 ...

如果用分做vi和m的单位,那就是整数了。

还可以做一些优化,不过不会有数量级上的变化了。28是我测试了穷举法能够在1分钟内执行完的一个值,看起来是给小了。
顶部
性别:未知-离线 Maxwell

代王
监管使
枢密直学士
山南西道节度使

Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27Rank: 27
柱国(正二品)
组别 诸侯
级别 征东将军
好贴 4
功绩 1845
帖子 5801
编号 622
注册 2004-7-7


发表于 2010-11-30 22:48 资料 文集 短消息 看全部作者


QUOTE:
原帖由 阿尔法孝直 于 2010-11-30 12:11 发表


我觉得题目表达有点奇怪:
按照出题的原意,似乎应该是:

有n种商品,单价分别为:
v1, v2, v3, v4, ..., vn
有现金m元,求解是否可以从n种商品中,每种选择若干件,总价正好为m元。

不过现在的题 ...

何谓出题原意?
顶部

正在浏览此帖的会员 - 共 1 人在线




当前时区 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

清除 Cookies - 联系我们 - 轩辕春秋 - Archiver - WAP