贪心算法 -- gone fishing
poj 1042 gone fishing
题目要求：
由有n个湖， 按照顺序排列，一个人从第一个湖向最后一个湖行进（方向只能从湖0到湖n-1），途中可以在湖中钓鱼。在每个湖中钓鱼时，开始的5分钟内可以钓到 f[i] 条，之后每5分钟钓到的鱼数目递减 d[i] ，且每两个相邻的湖的距离 t[i] 给出（t[i] 表示 由第 i 个湖向第 i + 1个湖行进在路上花费5分钟的倍数的时间， 即如果t[3] = 4，则表示从第三个湖向第四个湖行进需要花费20分钟）。 现给定总时间h 小时，求出在每个湖钓鱼时间的最好的方案，使得钓鱼的总数最多，如果两种方案结果相同，则输出在较小序号的湖中钓鱼时间更多的那个。
题目分析：
最优化问题，可以选择动态规划或者贪心算法，初看起来，是个多阶段的决策问题，且每个阶段会对下一个阶段产生影响，并不好找到合适的贪心策略，更适合采用动态规划。先考虑动态规划算法，可以考虑 动规数组 dp[t][n] 表示在 t 时刻到达湖 n 时之前钓鱼结果的最优值，可以找出递推关系式 dp[t][n] = max{ dp[t1][n-1] + fish_result(n-1, t - t1 - t[n-1])}
即对到达湖 n - 1的时刻 t1 进行枚举（在一定的范围之内，小于 t - t[n-1], 大于xx），然后取出最大值作为 dp[t][n]，这样从 n - 1 推到 n。
个人认为这种动态规划的方法是可行的，但是。。由于水平太菜。。没有成功。。
考虑采用贪心的算法来实现，仔细分析一下，当确定了需要到达的湖的个数n，也就确定了在路上需要消耗的时间，从而得到钓鱼的总时间，这样在规定的时间内钓鱼，每次都选择当前5分钟内收益最大的那个湖进行钓鱼（可以采用优先级队列 priority_queue 来实现）。 考虑到这样做会有可能出现先在湖 A 中钓鱼，再在湖B中钓鱼，然后再回到湖A中钓鱼... 但是这样不会影响最终的结果（这也是贪心算法可以运用到此题的前提）。因为，虽然只能从湖0到湖n-1行进，此时进行贪心选择虽然每次选择的顺序可能不断颠倒变化，但是这只是确定湖A有几次被选中钓鱼，也就是确定从湖0到湖n-1每个湖中钓鱼的时间。在实际行进途中钓鱼的时候，就按照贪心算出来的方案（在湖 i 中钓鱼几次），在途中的湖中钓鱼。
通过固定要经过的湖的个数n，将每个湖由于在路上消耗时间的差异去掉，使得面临的选择无差异，可以运用贪心算法。
实现代码：
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
#define MAX_INTERVAL_NUM 200
#define MAX_LAKE_NUM 25
int dist_time[MAX_LAKE_NUM];
int min_dist_time[MAX_LAKE_NUM];
int stay_times[MAX_LAKE_NUM];
int init_num[MAX_LAKE_NUM];
int dec_num[MAX_LAKE_NUM];
struct LakeNode{
int lake_index;
int cur_fish_amount;
int dec_amount;
int stay_time;
};
LakeNode lake_nodes[MAX_LAKE_NUM];
struct cmp{
bool operator() (LakeNode* lake1, LakeNode* lake2){
if (lake1->cur_fish_amount == lake2->cur_fish_amount){
return lake1->lake_index > lake2->lake_index;
}
return lake1->cur_fish_amount < lake2->cur_fish_amount;
}
};
void ClearQueue(priority_queue<LakeNode*, vector<LakeNode*>, cmp>& queue){
while(! queue.empty()){
queue.pop();
}
}
int Resolve(int N, int T){
priority_queue<LakeNode*, vector<LakeNode*>, cmp> lake_queue;
LakeNode* lake;
int result = 0, max_amount = 0;
stay_times[0] = T;
for (int n = 1; n <= N; n ++){
result = 0;
int fish_time = T - min_dist_time[n - 1];
if (fish_time <= 0){
break;
}
ClearQueue(lake_queue);
for(int i = 0; i < n; i ++){
lake_nodes[i].stay_time = 0;
lake_nodes[i].lake_index = i;
lake_nodes[i].cur_fish_amount = init_num[i];
lake_nodes[i].dec_amount = dec_num[i];
lake_queue.push((LakeNode*)&lake_nodes[i]);
}
while(! lake_queue.empty() && fish_time > 0){
lake = lake_queue.top();
lake_queue.pop();
if (lake->cur_fish_amount > 0){
result += lake->cur_fish_amount;
lake->cur_fish_amount -= lake->dec_amount;
}
if (lake->cur_fish_amount <= 0){
lake->cur_fish_amount = 0;
}
lake->stay_time ++;
fish_time --;
lake_queue.push(lake);
}
if (result > max_amount){
max_amount = result;
for(int i = 0; i < n; i ++){
stay_times[i] = lake_nodes[i].stay_time;
}
}
}
return max_amount;
}
int main(){
int n, h;
while(true){
cin >> n;
if (n == 0){
break;
}
cin >> h;
h = h*12;
for(int i = 0; i < n ; i ++){
cin >> init_num[i];
stay_times[i] = 0;
}
for(int i = 0; i < n; i ++){
cin >> dec_num[i];
}
min_dist_time[0] = 0;
cin >> dist_time[0];
for(int i = 1; i < n - 1; i ++){
cin >> dist_time[i];
min_dist_time[i] = min_dist_time[i - 1] + dist_time[i-1];
}
min_dist_time[n-1] = min_dist_time[n-2] + dist_time[n-2];
int result = Resolve(n, h);
cout << stay_times[0]*5 ;
for(int i = 1; i < n; i ++){
cout << ", " << stay_times[i]*5;
}
cout << endl << "Number of fish expected: " << result << endl << endl;
}
return 0;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
