
标题: 一个简单的算法题 [打印本页]
作者:
Maxwell 时间: 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 编辑 ]
作者:
zhaohaidao 时间: 2010-11-29 00:01
标记下,尝试用下贪心算法。。
作者:
Maxwell 时间: 2010-11-29 23:37
原帖由
zhaohaidao 于 2010-11-29 00:01 发表
标记下,尝试用下贪心算法。。
贪心算法可以考虑,不过就是可能无法找到所有解。
作者:
周瑜 时间: 2010-11-29 23:53
我用递归法把程序写出来了,可惜复杂度太高,对于 n=60 无能为力。
作者:
Maxwell 时间: 2010-11-30 00:01
原帖由 周瑜 于 2010-11-29 23:53 发表
我用递归法把程序写出来了,可惜复杂度太高,对于 n=60 无能为力。
目前改为n <= 28了,其实没有仔细算过n应该取多少合适,你自己选择一个上限也没问题
作者:
周瑜 时间: 2010-11-30 00:11
代码如下,对于最糟糕的情况,28个1中找出总金额和为14的物品,不打印的情况下运行两秒完成,找出40116600种结果。
void printSum(double candidates[], int index[], int n)
{
for (int i = 0; i < n; i++)
cout << candidates[index[i]] << " ";
cout << endl;
}
void getsum_help(double target, double sum, double candidates[], int size, int index[], int n)
{
if (sum > target)
return;
if (fabs(sum-target) <= 1e-6*fabs(target))
printSum(candidates, index, n);
int starti = n==0 ? 0 : index[n-1]+1;
for (int i = starti; i < size; i++)
{
index[n] = i;
getsum_help(target, sum + candidates[i], candidates, size, index, n+1);
}
}
void getsum(double target, double candidates[], int size)
{
int *index = new int[size];
getsum_help(target, 0, candidates, size, index, 0);
delete []index;
}
作者:
周瑜 时间: 2010-11-30 00:18
由于 vi 和 m 都是浮点数,因此也就断绝了我使用动态规划的想法。
上述代码可能的优化包括:
1.先对 candidates 数组进行降序排列,这样前几步更容易得到超过 target 值的和,假设所有价格均为正数,则立即返回。
2.每一步比较当前总和与剩下所有数的和是否比 target 更小,如果更小,则理论上都不可能达到,立即返回。
作者:
dimeterio 时间: 2010-11-30 07:49
先作幾個判斷,進行預處理,速度是不是會快一點?
首先對Vi進行升序排列。
然後判斷,找出Min(Vn>m),把Vi>=Vn都剔除;
然後從V1開始累加,找出“最多多少個價格之和<=m”,然後決定不再對更多個價格累加進行嘗試。
作者:
阿尔法孝直 时间: 2010-11-30 12:11
原帖由 Maxwell 于 2010-11-28 15:02 发表
有n件商品,价格分别为:
v1, v2, v3, v4, ..., vn
有现金m元,求解是否可以从n件商品中选择若干件价格正好为m元。
求所有符合要求的组合,并输出每种组合中若干件商品的序号,若无符合要求的组合,输出无解 ...
我觉得题目表达有点奇怪:
按照出题的原意,似乎应该是:
有n种商品,单价分别为:
v1, v2, v3, v4, ..., vn
有现金m元,求解是否可以从n种商品中,每种选择若干件,总价正好为m元。
不过现在的题目表达的意思,似乎是,
有n种商品,单价分别为:
v1, v2, v3, v4, ..., vn
有现金m元,求解是否可以从n种商品中,每种选择一件,总价正好为m元。
作者:
周瑜 时间: 2010-11-30 12:29
我认为题目没有歧义,从v1到vn的n件商品选择若干件,每件商品都是唯一的,但可能有多件商品价值相等。
如果按照楼上的第一种理解,解题方法也非常相似,把我代码中 starti 处的 +1 去掉即可。
[ 本帖最后由 周瑜 于 2010-11-30 08:42 编辑 ]
作者:
Maxwell 时间: 2010-11-30 22:46
原帖由 周瑜 于 2010-11-30 00:18 发表
由于 vi 和 m 都是浮点数,因此也就断绝了我使用动态规划的想法。
上述代码可能的优化包括:
1.先对 candidates 数组进行降序排列,这样前几步更容易得到超过 target 值的和,假设所有价格均为正数,则立即 ...
如果用分做vi和m的单位,那就是整数了。
还可以做一些优化,不过不会有数量级上的变化了。28是我测试了穷举法能够在1分钟内执行完的一个值,看起来是给小了。
作者:
Maxwell 时间: 2010-11-30 22:48
原帖由 阿尔法孝直 于 2010-11-30 12:11 发表
我觉得题目表达有点奇怪:
按照出题的原意,似乎应该是:
有n种商品,单价分别为:
v1, v2, v3, v4, ..., vn
有现金m元,求解是否可以从n种商品中,每种选择若干件,总价正好为m元。
不过现在的题 ...
何谓出题原意?
欢迎光临 轩辕春秋文化论坛 (http://www.xycq.org.cn/forum/) |
Powered by Discuz! 5.0.0 |