目錄
一、實驗目的
二、實驗內容
三、問題分析與求解
四、AC源代碼、截圖
五、實驗小結
一、實驗目的
1、了解貪心算法的分析過程，學會用貪心算法解決一些具體的問題。
2、了解廣度優先算法和深度優先算法。
二、實驗內容
- 1992
當然，我們的收藏中至少需要一個電腦游戲。典型的可以說是“鎮上追逐”。在我們的案例中，笑臉叫杰克，正在穿過分成小田野的小鎮。有些田地被墻覆蓋，無法穿過它們。杰克收集積分，并試圖避免與追逐他的怪物接觸。一旦杰克吃了特殊點（或星號），情況就會顛倒過來，杰克可以吃怪物。以此類推，一次又一次。我相信你們每個人都見過這樣的游戲。
在我們的例子中，城鎮是隨機生成的。杰克總是從左上角開始，“獎勵星號”在右下角。在最困難的關卡中，只要杰克只向左和向下走幾步，獎金就會消失，這些步數恰好足以從一個角落到另一個角落。如果他朝著錯誤的方向邁出一步，他永遠無法及時到達那里。但防止被怪物抓住仍然很重要。因此，玩家必須選擇最好的方式到達右下角。你要確定鎮上有多少種不同的方式。
- 1042
約翰要去釣魚。他有 h 小時可用 （1 <= h <= 16），該地區有 n 個湖泊 （2 <= n <= 25），都可以沿著一條單行道到達。約翰從1號湖開始，但他可以在任何他想要的湖結束。他只能從一個湖到下一個湖，但除非他愿意，否則他不必在任何湖停留。對于每個 i = 1,...,n - 1，從湖泊 i 到湖泊 i + 1 所需的 5 分鐘間隔數表示為 ti （0 < ti <=192）。例如，t3 = 4 表示從湖 3 到湖 4 需要 20 分鐘。為了幫助計劃他的釣魚之旅，約翰收集了一些關于湖泊的信息。對于每個湖泊i，預計在最初的5分鐘內捕獲的魚的數量，記作fi（fi >= 0），是已知的。
每釣魚 5 分鐘，預計在接下來的 5 分鐘間隔內捕獲的魚數量就會以恒定的 di （di >= 0） 速率減少。如果預計在一個區間內捕獲的魚的數量小于或等于di，則在下一個區間內湖中將不再有魚。為了簡化計劃，約翰假設沒有其他人會在湖邊釣魚，以影響他預計捕獲的魚的數量。
編寫一個程序來幫助約翰計劃他的釣魚之旅，以最大限度地增加預期捕獲的魚的數量。在每個湖泊花費的分鐘數必須是 5 的倍數。
三、問題分析與求解
1.1992分析與求解：
? ? ? ?這道題是問你有多少種能最快到達終點的方法。注意這里的最快不是相對是最快。而是路線只能向右或者向下 不允許向上或者向左走。
2.1042分析與求解：
? ? ? ?我們可以把總時間分為兩個部分：在路上的時間和在釣魚的時間。由于路是單行的，所以在路上的時間取決于走的最遠距離，即到達的池塘的最大編號。 剩余的時間用于釣魚。我們可以把移動+釣魚的混合過程拆分為移動的過程和釣魚的過程，即指定一個池塘為終點，移動過程即從起點到終點的過程，釣魚的過程就是從起點到終點的各個池塘中選擇池塘釣魚，因為移動過程所需的時間已經在前面考慮過了，這個時候我們就可以認為需要移動的時候可以直接瞬間到達。然后，選擇到哪些池塘釣魚的策略采用貪心的方法，每個釣魚的5分鐘都選擇期望最大的那一個池塘，每在選擇一個池塘釣魚5分鐘，減少相應池塘的期望，增加計劃中在該池塘釣魚的時間，然后繼續選擇期望最大的池塘，直到釣魚的時間不夠，或者池塘里沒有魚了。如果池塘沒有魚了，還有時間的話，把多余的時間分配給第一個池塘。
四、AC源代碼、截圖
#include<stdio.h>
#include<malloc.h>
#include<string.h>typedef struct{int x, y;
}Point;typedef struct{Point Q[1100];int top, tail;
}Que;
Que q;void ini() {q.top = 0, q.tail = 0;}
void push(int x, int y) {q.Q[q.tail].x = x, q.Q[q.tail].y = y;q.tail++; if(q.tail > 1099) q.tail = 0;}
Point pop() {Point tt; tt = q.Q[q.top++]; if(q.top > 1099) q.top = 0; return tt;}
bool empty() {if(q.tail == q.top) return 1; return 0;}int R, S;
bool map[1005][1005];
int f[1005][1005];int main()
{int Case;int i, j;char x;Point tt;while(scanf("%d", &Case) != EOF){while(Case--){scanf("%d%d", &R, &S);for(i = 0; i < R; ++i){getchar();for(j = 0; j < S; ++j){scanf("%c", &x);map[i][j] = (x == '.'? 1 : 0);f[i][j] = 0;}}push(0, 0);f[0][0] = 1;while(!empty()){tt = pop();if(map[tt.x + 1][tt.y]){if(!f[tt.x + 1][tt.y]) push(tt.x + 1, tt.y);f[tt.x + 1][tt.y] += f[tt.x][tt.y];}if(map[tt.x][tt.y + 1]){if(!f[tt.x][tt.y + 1]) push(tt.x, tt.y + 1);f[tt.x][tt.y + 1] += f[tt.x][tt.y];}}printf("Existuje %d ruznych cest.\n", f[R - 1][S - 1]);}}return 0;
}
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
using namespace std;const int N=25;
int n,h;
int f[N],d[N],t[N];//f第一個五分鐘釣的魚量，d為每個五分鐘減少的魚量，t為i到i+1五分鐘的個數
int ans;
int each[N];//記錄最終每條湖用的時間
int tans,teach[N];//最優釣魚量和各湖釣魚時間
int th,tf[N];//有效釣魚時間和每條湖前五分鐘的釣魚量 int main()
{int i,j;while(cin>>n&&n>0){//當湖的數量為0的時候結束 cin>>h;//輸入時間 for(i=0;i<n;i++){cin>>f[i];//第一次的魚量 } for(i=0;i<n;i++){cin>>d[i];//每五分鐘減少的魚量 }for(i=0;i<n-1;i++){cin>>t[i];//每個湖間距離需要的時間片 }h*=12;//一小時12個時間片ans=-1;for(i=0;i<n;i++){//表示再第i條湖停下來 //初始化每一次貪心th=h;//有效時間先初始化為總時間 for(j=0;j<n;j++){tf[j]=f[j];//每條湖初始的釣魚量初始為第一次五分鐘的釣魚量 teach[j]=0;//每個湖的釣魚時間初始化為0 } tans=0;//最大釣魚數初始化為0 //對每五分鐘貪心選擇釣魚量最大的湖釣魚 while(th>0){//當有效時間大于0 int ind=0,max=tf[0];//令第一條湖的魚量為最大值 ，ind標記湖是第幾條湖 for(j=0;j<=i;j++){if(tf[j]>max){//不考慮順序先找第一次魚量最大的湖 max=tf[j];ind=j;}}if(max==0){//最大釣魚量為0時，將剩余的釣魚時間加到第一個湖上的釣魚時間 teach[0]+=th*5;//例如樣例一 break;}else{teach[ind]+=5;//最大湖的釣魚時間，每釣一次加一次五 tans+=tf[ind];//加上最大魚量的湖的該次的魚數 if(tf[ind]>=d[ind])//如果魚量不少于減少的魚數 ，則減 {tf[ind]-=d[ind];}else{tf[ind]=0;//小于減少數則賦值為0 }} th--;//有效時間減少一個時間片(一個時間片五分鐘) }if(i!=n-1){//i的話是表示在第i條湖停下來 h-=t[i];//減去到下一條湖的時間片 }if(tans>ans){//如果值大于前面的值，就把值賦給ans ans=tans;for(j=0;j<n;j++){each[j]=teach[j];//記錄最終每條湖用的時間 }}} cout<<each[0]; for(i=1;i<n;i++){cout<<", "<<each[i];}cout<<endl;cout<<"Number of fish expected: "<<ans<<endl;cout<<endl;}return 0;
} 
五、實驗小結
1.迷宮問題最短路徑問題中，每次處理的位置所對應的距離是嚴格遞增的，因此，一旦找到終點，當前的距離就是最短距離，
搜索可移動到的位置中，判斷條件不僅僅是不碰壁不超邊界，還有一個條件就是沒有到達過。因為，如果已經到達了這個位置，這說明已經有更短的路徑到達了這個位置，這次到達這個位置的路徑是更遠的，不可能達到最優解；
2.貪心算法存在的問題：
（1）不能保證求得的最后解是最佳的；
（2）不能用來求最大值或最小值的問題；
（3）只能求滿足某些約束條件的可行解的范圍。
)
