Bank问题的算法正确性
Bank问题的算法正确性
提问于 2019-01-22 01:47:59
这是我所指的问题。简短的总结：
输入:整数时间(T)；银行关闭的时间(以分钟为单位)，以及一组对( c )和t (表示此人携带的现金(整数)的数量)，以及从现在起的时间(以分钟为单位)。为一个人服务需要一分钟，你必须最迟开始为一个人服务，t。
输出:可以在关闭时间内收集的最大金额。
我的方法是:把所有的人都放在一张地图上，把钱和时间联系起来。我把这张地图按钱分类。然后，我做了一个排队式的结构，在那里我带着钱最多的人，把他/她尽可能地放回去。如果这个地方被占了，我就往前走，直到找到一个位置。如果我不能，那我就是不加那个人。
下面是我的助手函数，用于确定我是否可以插入一个人。
// returns index where we can insert, otherwise -1
int canInsert(bool* queue, int timeToInsert) {
if (!queue[timeToInsert]) {
return timeToInsert;
} else {
int index = timeToInsert-1;
while (index >= 0) {
if (!queue[index]) {
return index;
} else {
index--;
}
}
return -1;
}
}以下是主要的驱动程序功能：
// moneyToTime is a map that maps a person's money to the time value
int Bank(int T, map<int, int> moneyToTime) {
int answer = 0;
bool queue[47] = {0};
for (map<int,int>::reverse_iterator i = moneyToTime.rbegin(); i != moneyToTime.rend(); i++) {
if (T > 0) {
// try to insert. If we can, then add to sum. Otherwise, don't.
int potentialIndex = canInsert(queue, i->second);
if (potentialIndex != -1) {
queue[potentialIndex] = 1;
answer += i->first;
T--;
}
} else {
break;
}
}
return answer;
}从逻辑上讲，这对我来说是有意义的，而且它几乎通过了所有的测试用例。有一对夫妇正在失败，我看不出他们是什么。测试用例错误实际上表明错误的答案，而不是糟糕的运行时错误。有人能帮我看出我的做法中的谬误吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2019-01-22 03:16:15
您没有展示如何构建moneyToTime，但无论如何，map<int, int>似乎是一个错误的类型。想象一下，你有很多人拥有同样数量的钱和不同的时间。那么，您将如何在您的moneyToTime中表示
如果我的理论是正确的，这样的一个例子应该会破坏你的解决方案：
3 3
2000 2
2000 1
500 2显然，最好的金额是4000 = 2000 + 2000。我想你只能拿到2500英镑。
Stack Overflow用户
发布于 2020-09-20 09:21:59
我认为TC的最佳金额是4500，
3 3
2000 2
2000 1
500 2{货币，时间} {2000,0} \ {2000,1} \ {500,2}
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/54300139
复制相关文章
相似问题
腾讯云开发者
