标题: 一个简单的算法题 [打印本页]
作者:
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 |