---
tags: APCS Preparation
---
# Greedy
## 什麼是Greedy?
* 只考慮目前狀態的最佳選擇，之前所選擇的解答不會影響到後面所選的解答
* 不斷選擇局部最佳解 -> 全部選取結束後就獲得整體的最佳解
## Greedy的解題步驟
### Step.1 定義貪婪準則
根據此貪婪準則，不斷找出目前小問題的最佳解
### Step.2 不斷重複貪婪準則，直到解決問題為止

## 工作排程問題
### Problem A
有$n$個工作可以執行，給定開始與結束時間，時間從0開始，開始與結束時間都是整數，只有一台機器可以執行且每次只能執行一份工作，工作一旦開始必須做完，已知不用考慮切換時間，問：執行完後最多有幾個工作被完成？

Sample Input
5
1 10
2 4
3 6
2 5
4 9

Sample Output
2

#### 原則：結束最早的工作先做！

#include<iostream>
#include<cstdlib>
using namespace std;
struct work
{
    int start;
    int end;
};
bool cmp(work a,work b)
{
    if(a.end == b.end)
    {
        return a.start<b.start;
    }
    
    return a.end<b.end;
}
int main()
{
    int n;
    while(cin>>n)
    {
        work arr[n];
        for(int i = 0; i < n; i++)
        {
            cin>>arr[i].start;
            cin>>arr[i].end;
        }
        
        sort(arr,arr+n,cmp);
        
        int ans = 1;
        int cur_time = arr[0].end;
        
        for(int j = 1; j < n; j++)
        {
            if(arr[j].start >= cur_time)
            {
                ans++;
                cur_time = arr[j].end;
            }
            
        }
        
        
        cout<<ans<<endl;
        
    }
}

### Problem B
有$n$個工作可以執行，給定開始與結束時間，工作時間可能重疊，時間從0開始，開始與結束時間都是整數，有$n$台機器可以執行且每次只能執行一份工作，工作可到每台機器去執行，且工作一旦開始必須做完，已知不用考慮切換時間，問：執行完後最少有幾台機器才能完成所有工作

Sample Input
5
1 10
2 4
3 6
2 5
4 9

Sample Output
4

#include<iostream>
#include<cstdlib>
using namespace std;
struct work
{
    int start;
    int end;
};
bool cmp(work a,work b)
{
    if(a.start == b.start)
    {
        return a.end<b.end;
    }
    
    return a.start<b.start;
}
int main()
{
    int n;
    while(cin>>n)
    {
        work arr[n];
        for(int i = 0; i < n; i++)
        {
            cin>>arr[i].start;
            cin>>arr[i].end;
        }
        
        sort(arr,arr+n,cmp);
        
        int ans = 1;
        int m[n];
        for (int x = 0;x<n;x++)
        {
            m[x] = -1;
        }
        
        m[0] = arr[0].end;
        
        for(int j = 1; j < n; j++)
        {
            for(int k=0;k<n;k++)
            {
                if(m[k]<=arr[j].start)
                {
                    m[k] = arr[j].end;
                    break;
                }
            }
            
        }
        
        int arc_ans = 0;
        for(int r=0;r<n;r++)
        {
            if(m[r] == -1)
                arc_ans++;
        }
        
        cout<<"arc:"<<arc_ans<<endl;
        ans = n-arc_ans;
        
        cout<<ans<<endl;
        
    
        
    }
}

### Problem C
有$n$個工作從開始就進入到機器，給予$n$個工作的執行所需時間，只有一台機器可以執行且每次只能執行一份工作，工作一旦開始必須做完，請計算完成工作的最小平均等待時間？

Sample Input
5
10
4
6
5
9

Sample Output
10.4

#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        int arr[n];
        for(int i=0;i<n;i++)
        {
            cin>>arr[i];
        }
        
        sort(arr,arr+n);
        
        int now_wait = 0;
        int total = 0;
        for(int j=0;j<n;j++)
        {
            int tmp = 0;
            for(int k=0;k<j;k++)
                tmp+=arr[k];
            now_wait = tmp;
            total += now_wait;
        }
        
        double avg = (double)(total)/n;
        cout<<avg<<endl;
    }
}

### Practice Problem Sets
- [ ] [ZJ a567](https://https://zerojudge.tw/ShowProblem?problemid=a567)

## Huffman Coding
### Basic Understanding
[Huffman Coding - Greedy Algorithm](https://https://www.youtube.com/watch?v=dM6us854Jk0)

<iframe width="560" height="315" src="https://www.youtube.com/embed/dM6us854Jk0" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

### Problem Statement
每次輸入數字$n$，$n$表示字元個數，輸入$n<26$，之後有$n$行分別是每一行為一個小寫英文字母與一個整數組成，小寫英文字母表示被編碼的字元，而整數出現的頻率，數值越大表示頻率越高

Output: 輸出每個小寫英文字母的編碼

Sample Input
5
a 10
b 4
c 5
d 7
e 8

Sample Output
d 00
e 01
b 100
c 101
a 11

### 解題思路
* Greedy:
* 每一個字母照frequency從小到大排序
* Merge:
* 使用deque，一次取出frequency（可能為字母也有可能是子 樹最小的前兩項並合併成為新的子樹
* 將新的子樹放回deque，按照上述步驟不斷排序到只剩一項（也代表已經合併完成為止）

* DFS:
* Traversal the whole tree
* 左邊為0，右邊為1

### Practice Code

#include <iostream>
#include<algorithm>
#include<deque>
using namespace std;
struct node
{
    int id; //節點的編號
    char ch; //字母
    int w;//frequency
    bool t; //判斷此節點是否為字元
    int le; //左子節點
    int ri; //右子節點
};
node hf[101];

deque<node> tmp;
char code[10];
bool cmp(node a,node b)
{
    return a.w<b.w;
}

void dfs(int id, int level)
{
    if(!hf[id].t)
    {
        code[level] = '0'; //往左邊為0
        dfs(hf[id].le,level+1);
        code[level] = '1'; //往右邊為1
        dfs(hf[id].ri,level+1);
    }
    else
    {
        //dfs終止：到達字母的葉
        cout<<hf[id].ch<<" ";
        for(int i=0;i<level;i++)
        {
            cout<<code[i];
        }
        cout<<endl;
    }
}


int main()
{
    int n,w,num;
    char c;
    while(cin>>n)
    {
        tmp.clear();
        for(int i=0;i<n;i++)
        {
            cin>>c>>w;
            hf[i].id = i;
            hf[i].ch = c;
            hf[i].w = w;
            hf[i].t = true;
            tmp.push_back(hf[i]);
        }
        
        num = n; //從第n項開始發放合併的結果
        sort(tmp.begin(),tmp.end(),cmp); //按照frequencies排序
        while(tmp.size()>1)
        {
            node a,b,s;
            //取出前面freqency最小的兩項
            a = tmp.front();
            tmp.pop_front();
            b = tmp.front();
            tmp.pop_front();
            
            //合併成好新的s
            s.id = num;
            s.t = false;
            s.le = a.id;
            s.ri = b.id;
            s.w = a.w+b.w;
            hf[num] = s;
            tmp.push_back(s);
            sort(tmp.begin(),tmp.end(),cmp);
            num++;
        }
        //當全部合併完畢會跳出while迴圈
        
        //遍歷求所有結果
        dfs(tmp[0].id,0);
    }
    
}

### Practice Problem Sets
- [x] [ZJ d371](https://zerojudge.tw/ShowProblem?problemid=d371)
- [x] [ZJ b606](https://zerojudge.tw/ShowProblem?problemid=b606)

### APCS

- [x] [ZJ c471](https://zerojudge.tw/ShowProblem?problemid=c471)

#include<iostream>
#include<cstdlib>
using namespace std;
struct node
{
    long long w;
    long long f;
};
bool cmp(node a,node b)
{
    return a.w*b.f < b.w*a.f; //代價小的排上面
    
}
int main()
{
    int n;
    while(cin>>n)
    {
        node item[n];
        for(int i=0;i<n;i++)
        {
            cin>>item[i].w;
        }
        
        for(int i=0;i<n;i++)
        {
            cin>>item[i].f;
        }
        
        
        sort(item,item+n,cmp);
        //cout<<"items"<<endl;
        /*for(int i=0;i<n;i++)
        {
            cout<<item[i].w<<" ";
        }
        cout<<"\n";
        */
        long long cost = 0;
        long long int acc = item[0].w; //頂上累積的量
        for(int i=1;i<n;i++)
        {
            cost += acc*item[i].f;
            acc+=item[i].w;
        }
        
        cout<<cost<<endl;
        
        
    }
    
}

## 可分割背包

假設有$n$個物品及一個背包，已知背包的負重能力與每個物品的價值與重量，可以將物品只取部分到背包，求在背包的負重範圍內放入背包所有物品的最大價值。

Input
每次輸入數字 $n$ ，$n$ 表示物品個數，之後有 $n$ 行，每一行兩個整數$w$與$v$，$w$表重量，$v$表價值。最後輸入一個整數$k$，表示背包的負重能力。

Output
輸出最大價值

Sample Input
5
3 10
3 4
1 5
2 7
3 8
5

Sample Output
18.66667

### 解題想法
按照**單位重量由大到小**排序，依序放到背包裡面
放到背包裝滿為止，最後一個**可以是被拆開的**
( ie. 可以放$2/3$ 顆蘋果到書包裡，這是合法的 )

#include<iostream>
#include<cstdlib>
using namespace std;
struct item
{
    int w;
    int v;
    double v_perw;
};
bool cmp(item a,item b)
{
    return a.v_perw > b.v_perw;
}
int main()
{
    int n;
    while(cin>>n)
    {
        item arr[n];
        for(int i=0;i<n;i++)
        {
            cin>>arr[i].w>>arr[i].v;
            arr[i].v_perw = (double)arr[i].v/(double)arr[i].w;
            //cout<<arr[i].v_perw<<endl;
        }
        int max;
        cin>>max;
        double sum = 0;
        sort(arr,arr+n,cmp);
        
        for(int j=0;j<n;j++)
        {
            if(arr[j].w <= max) //全放
            {
                max -= arr[j].w;
                sum += (double)arr[j].v;
                //cout<<"max:"<<max<<endl;
                
            }
            
            else//切著放
            {
                double tmp = (double)max/(double)arr[j].w;
                tmp *= arr[j].v;
                
                sum += tmp;
                break;
            }
            
            
            
        }
        cout<<sum<<endl;
        
        
        
    }
}