一个简单的算法题 - 设计与修改 - 轩辕春秋文化论坛 20周年


	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分钟内执行完的一个值，看起来是给小了。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	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元。

不过现在的题 ...

何谓出题原意？

[广告] 真诚支持说岳，携手共创辉煌