引入

这是社团面试的题目

题目如下

贪心的黄老板

又到了月底,黄老板的手头开始紧张,所以他计划在各个城市之间打起了赚钱的想法。
想 用 x 元 钱去买 a 物品,再 把 a 物品 拿到另一个城市去贩卖,在买 b 物品 以此进行下
去 最后再把东西卖了 ,得到最大利润(不计任何其他一切费用 任务物品可以分割为
很细小的一块,同时,每个物品或钱最多只能进行一次买卖,特别请注意:一旦将物品
转换为钱,则交易就结束了 。
输入描述: 每组数据第一行输入一个n(n<=10000)(表示x元钱)和一个m(m<=10000) (表示接下来有m组兑换关系) 接下来有m组数据a,b,c(0<=a,b<=1000000,0<=c<=2;输入过程中当a或b为0时表示为钱)
注意:输入中没给出的兑换关系表示不能兑换,兑换过程中物品都将全部兑换,兑换过
程中不会出现循环。
*输出描述: 输出黄老板最后能赚到的最多的钱数。(保留2位有效数字;最后结果中不会超过2^31 – 1)

输入样例:

5000 5
0 1 1.2
1 2 1.3
1 3 1.4
2 0 1.4
3 0 1.5

输出样例: 12600.00

提示:本题解法不唯一。参考解法如下:建议先了解数据结构中的图结构对所有数据进
行建模,再对数据进行整理并利用动态规划求利润最大值。(想想本题的数据可以用哪
种图建模,对应着哪个经典算法?)

尝试解答

对于目前还没有系统学习数据结果和算法的菜鸟来说,我只会用递归来解。

代码如下(代码高亮有问题...to be fixed)

#include <stdio.h>

typedef struct {
    int a;
    int b;
    double rate;
} Trans;

int cur;

double getMaxSum(Trans* T, double sum, int n, int s) {
    double max = sum;
    bool moved = false;
    for (int i = s; i < n; ++i) {
        if (cur == T[i].a) {
            moved = true;
            double tmp;
            cur = T[i].b;
            if (cur == 0) {
                tmp = sum * T[i].rate;
            }
            else {
                tmp = getMaxSum(T, sum * T[i].rate, n, 0);
                if (tmp < 0) {
                    moved = false;
                }
            }
            if (max < tmp) {
                max = tmp;
            }
            cur = T[i].a;
        }
    }
    if (!moved && max == sum) {
        return -1;
    }
    return max;
}

int main() {
    double sum;
    int m;
    scanf("%lf %d", &sum, &m);
    Trans T[m];
    for (int i = 0; i < m; i++) {
        int a, b;
        double r;
        scanf("%d %d %lf", &a, &b, &r);
        T[i].a = a;
        T[i].b = b;
        T[i].rate = r;
    }

    printf("%.2lf", getMaxSum(T, sum, m, 0));

    return 0;
}

然而代码可以过社团搭建oj,却过不了学习的oj
一定有问题的。
不过暂时的我发现不出来。

Solution

需要拓扑排序+动态规划

但是目前技能点有限,实在无法顾及。

等有时间再把这个坑填上去吧。

To be continued

Last modification:November 22nd, 2019 at 11:42 am
要饭啦~