主题:关于一道题的算法~
moriaty
[专家分:0] 发布于 2010-10-15 16:30:00
有这样一道题:
有一天你想去买书,总共带了有M元,结果你到了书店之后,发现了有n本书你都想买,但是这n本书的价格总和超过了你带的钱,现在你想要让花的钱最接近M元,请列出这种买书的方案,编程实现。
我先把各本书的价格从高到低排了一遍,然后试过各种算法,就是做不出来。
我主要是觉得做这种题的时候思路非常混乱。
有没有高手可以提供一个好的算法思路?
谢谢!
回复列表 (共3个回复)
沙发
sponge [专家分:30] 发布于 2010-10-15 17:35:00
动态规划
板凳
langxve [专家分:80] 发布于 2010-10-16 13:53:00
排列组合的算法,用一个数组保存所有数目的价格,然后从中去掉一本的价格,剩余的数目价格总和与m对比,比较其大小,然后去掉两本,三本......
当总和最接近m为止。不过如果n比较小可以用多层for循环,如果n大了那就要用递归了。
思路很清晰,递归不好设计!
在思考中。。。。。。
3 楼
eastcowboy [专家分:25370] 发布于 2010-10-16 20:32:00
排序不一定有用,下面这两种解法都是不需要排序的。
其实这两种解法都在1楼2楼分别给出了,只是说得太简略。
两种办法都可以得出正确结果,但各有优缺点。
解法一:排列组合。
也就是分别决定每本书要不要买,然后计算价格是否符合,找出最佳的选择即可。
递归说穿了也不算太难。
// 找出从第i本书到第n本书的最佳选择。也就是所剩的钱越少越好,但不能小于零
// 参数说明:
// n是书的总数
// price_list是每本书的价格
// i是当前判断第i本书
// money是买下前面的书之后所剩的钱
// 返回值是所有书都判断完毕之后所剩的钱,根据题目要求,所剩的钱越少越好,但不能小于零
int f(int n, int price_list[], int i, int money) {
// 如果已经判断完所有的书,直接返回。
if (i == n) {
return money;
}
// 如果第i本书不买
// 找出接下来的书的最佳选择,记录下所剩余的钱数
int tmp1 = f(n, price_list, i + 1, money);
// 如果第i本书要买
// 找出接下来的书的最佳选择,记录下所剩余的钱数
// 注意:如果钱不够,则无法买,不进行递归
if (money >= price_list[i]) {
int tmp2 = f(n, price_list, i + 1, money - price_list[i]);
// 如果买比不买更佳
if (tmp1 > tmp2) {
tmp1 = tmp2;
}
}
return tmp1;
}
int main() {
int price[] = {100, 60, 60};
printf("%d\n", f(3, price, 0, 125));
return 0;
}
解法二:动态规划。
设置一个数组,大小为M + 1。
如果能花k元买到若干书,并且不剩钱,则设置数组的第k个元素为1,否则设置数组的第k个元素为零。
想办法把这个数组计算出来,然后就很容易得出结果了(倒着找,找到第一个为1的元素即为所花的钱。然后可算出所剩的钱)
int f(int n, int price_list[], int money) {
int* arr = new int[money + 1];
int i;
for (i = 0; i <= money; ++i) {
arr[i] = 0;
}
arr[0] = 1;
// 若花k元可以买若干本书(并且不剩钱),则花k + price_list[i]元也可以买若干本书(并且不剩钱)
for (i = 0; i < n; ++i) {
int price = price_list[i];
for (int k = money - price; k >= 0; --k) {
if (arr[k] != 0) {
arr[k + price] = 1;
}
}
}
// r: 最多可以花掉的钱
int r = money;
while (arr[r] == 0) {
--r;
}
delete[] arr;
// money - r: 所剩的钱
return money - r;
}
评价:
从难易角度讲,解法一稍微简单一点,并且不容易出错。
从算法的观点来看,解法二的时间复杂度低,适用于n很大的情形。但如果M也很大,那性能会有明显下降。如果书的价格、钱的总数不是整数,则解法二就难以凑效。
对于解法一,时间复杂度很高,如果n超过20,则计算起来需要花费很长时间。但M的大小不会对计算时间造成影响。书的价格、钱的总数及是不是整数,也没有太大影响,只需要把int修改为double即可。
楼主可以看一些关于算法的入门书籍。
我来回复