回 帖 发 新 帖 刷新版面

主题:关于一道题的算法~

有这样一道题:
有一天你想去买书,总共带了有M元,结果你到了书店之后,发现了有n本书你都想买,但是这n本书的价格总和超过了你带的钱,现在你想要让花的钱最接近M元,请列出这种买书的方案,编程实现。

我先把各本书的价格从高到低排了一遍,然后试过各种算法,就是做不出来。

我主要是觉得做这种题的时候思路非常混乱。
有没有高手可以提供一个好的算法思路?

谢谢!

回复列表 (共3个回复)

沙发

动态规划

板凳

排列组合的算法,用一个数组保存所有数目的价格,然后从中去掉一本的价格,剩余的数目价格总和与m对比,比较其大小,然后去掉两本,三本......
当总和最接近m为止。不过如果n比较小可以用多层for循环,如果n大了那就要用递归了。
思路很清晰,递归不好设计!
在思考中。。。。。。

3 楼

排序不一定有用,下面这两种解法都是不需要排序的。
其实这两种解法都在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即可。

楼主可以看一些关于算法的入门书籍。

我来回复

您尚未登录,请登录后再回复。点此登录或注册