《原神攻略》有香自西來角色喜好食譜整理

  • Z时代
  • 2024-01-10
  • 分类：游戏

貪心演算法的定義：
貪心演算法是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，只做出在某種意義上的區域性最優解。貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。
解題的一般步驟是：
1.建立數學模型來描述問題；
2.把求解的問題分成若干個子問題；
3.對每一子問題求解，得到子問題的區域性最優解；
4.把子問題的區域性最優解合成原來問題的一個解。
如果大家比較瞭解動態規劃，就會發現它們之間的相似之處。最優解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的。貪心演算法和動態規劃本質上是對子問題樹的一種修剪，兩種演算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的)。動態規劃方法代表了這一類問題的一般解法，我們自底向上構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值捨棄。而貪心演算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優的路，一直走到底就可以了。
話不多說，我們來看幾個具體的例子慢慢理解它：
1.活動選擇問題
這是《演算法導論》上的例子，也是一個非常經典的問題。有n個需要在同一天使用同一個教室的活動a1,a2,…,an，教室同一時刻只能由一個活動使用。每個活動ai都有一個開始時間si和結束時間fi 。一旦被選擇後，活動ai就佔據半開時間區間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個活動就可以被安排在這一天。該問題就是要安排這些活動使得儘量多的活動能不衝突的舉行。例如下圖所示的活動集合S，其中各項活動按照結束時間單調遞增排序。

考慮使用貪心演算法的解法。為了方便，我們用不同顏色的線條代表每個活動，線條的長度就是活動所佔據的時間段，藍色的線條表示我們已經選擇的活動；紅色的線條表示我們沒有選擇的活動。
如果我們每次都選擇開始時間最早的活動，不能得到最優解：

 如果我們每次都選擇開始時間最早的活動，不能得到最優解：


可以用數學歸納法證明，我們的貪心策略應該是每次選取結束時間最早的活動。直觀上也很好理解，按這種方法選擇相容活動為未安排活動留下儘可能多的時間。這也是把各項活動按照結束時間單調遞增排序的原因。

#include<cstdio>
#include<iostream>
#include<algorithm> 
usingnamespace std;    
int N;
struct Act
{
int start;
int end;
}act[100010];
bool cmp(Act a,Act b)  
{  
return a.end<b.end;  
} 
int greedy_activity_selector()  
{  
int num=1,i=1;   
for(int j=2;j<=N;j++)  
    {  
if(act[j].start>=act[i].end)  
        {  
            i=j;  
            num++;  
        }  
    }  
return num;
}
int main()  
{  
int t;
    scanf("%d",&t);
while(t--)
    {
        scanf("%d",&N);
for(int i=1;i<=N;i++)
        {
            scanf("%lld %lld",&act[i].start,&act[i].end);
        }
        act[0].start=-1;
        act[0].end=-1;
         sort(act+1,act+N+1,cmp); 
int res=greedy_activity_selector();
        cout<<res<<endl;  
    }
}

2.錢幣找零問題
這個問題在我們的日常生活中就更加普遍了。假設1元、2元、5元、10元、20元、50元、100元的紙幣分別有c0, c1, c2, c3, c4, c5, c6張。現在要用這些錢來支付K元，至少要用多少張紙幣？用貪心演算法的思想，很顯然，每一步儘可能用面值大的紙幣即可。在日常生活中我們自然而然也是這麼做的。在程式中已經事先將Value按照從小到大的順序排好。

#include<iostream>
#include<algorithm>
usingnamespace std;
constint N=7; 
int Count[N]={3,0,2,1,0,3,5};
int Value[N]={1,2,5,10,20,50,100};
int solve(int money) 
{
int num=0;
for(int i=N-1;i>=0;i--) 
    {
int c=min(money/Value[i],Count[i]);
        money=money-c*Value[i];
        num+=c;
    }
if(money>0) num=-1;
return num;
}
int main() 
{
int money;
    cin>>money;
int res=solve(money);
if(res!=-1) cout<<res<<endl;
else cout<<"NO"<<endl;
}



以上是 《原神攻略》有香自西來角色喜好食譜整理 的全部内容， 来源链接： utcz.com/yxgl/576397.html

回到顶部