Boil's Blog HomeArchivesTagsCategories
贪心第一讲
Word count: 2.1k|Reading time: 9 min

多元哈夫曼编码(homework)

题目内容

问题描述：在一个操场的四周摆放着n堆石子，现要将石子有次序地合并成一堆。规定每次至少选2堆至多选k堆石子合并成新的一堆，
合并的费用为新的一堆石子数。计算出将n堆石子合并成一堆的最大总费用和最小总费用。
算法设计：对于给定的n堆石子，计算合并成一堆的最大总费用和最小总费用。
数据输入：文件的第1行有2个正整数n和k，表示有n堆石子，每次至少选2堆至多选k堆石子合并。第2行有n个数，分别表示每堆石子的个数。
输入示例：
7 3
45 13 12 16 9 5 22
输出示例：
593 199

实现思路

简单哈夫曼编码问题的推广。这里实现的关键就在于优先队列的使用。对于最小值，我们只需要每次取小根堆优先队列的前k项求和，删去这k项，转而将其和放入即可。一旦在某一次（包括刚开始），剩下的项数小于等于K，那么就是一次合并，统计输出。而最大值就是变为大根堆的优先队列，并且固定k为2.

实现细节

在加的时候注意，每次k项的相加都要加到累加器中

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//
//  9th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/4/21.
//
//

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x))

priority_queue<int,vector<int>,greater<int>> q1;
priority_queue<int,vector<int>,less<int>> q2;

int min_cost(int n,int k)
{
    int cost=0;
    while(1)
    {
        if (q1.size()<=k)
        {
            while(!q1.empty())
            {
                cost+=q1.top();
                q1.pop();
            }
            return cost;
        }
        int tmp=0;
        for (int i=1;i<=k;i++)
        {
            tmp += q1.top();
            q1.pop();
        }
        cost+=tmp;
        q1.push(tmp);
    }
    return -1;
}

int max_cost(int n)
{
    int cost=0;
    while(1)
    {
        if (q2.size()<=2)
        {
            while(!q2.empty())
            {
                cost+=q2.top();
                q2.pop();
            }
            return cost;
        }
        int tmp=0;
        for (int i=1;i<=2;i++)
        {
            tmp += q2.top();
            q2.pop();
        }
        cost+=tmp;
        q2.push(tmp);
    }
    return -1;
}


int main()
{
    int n,k;
    cin >> n >> k;
    int tmp;
    for (int i=1;i<=n;i++)
    {
        cin >> tmp;
        q1.push(tmp);
        q2.push(tmp);
    }
    cout << max_cost(n)  << " " << min_cost(n, k) << endl;
}

克鲁斯卡尔算法的实现(homework)

题目内容

最小生成树的一个经典算法。也就是给出一个图让我们求其最小生成树

实现思路

克鲁斯卡尔算法的核心其实就是贪心算法。我们首先对所有边进行从小到大排序，每次从小到达选边，如果这条边的加入不会导致这个图中出现回路，那么我们就选，否则就不选。知道图中所有的点都加到一个连通图中。为了每次加入判断是否有回路：我们在这里使用经典的并查集算法。设置一个fa数组，表示每个点的祖先，开始的时候祖先均为自己本身。设置一个ran数组，用来记录每个祖先节点往下的层数是多少。因为我们在合并的时候需要考虑把小层数的合并到大层数的，如果二者相等则需要把层数加1。

实现细节

实现的关键部分在于每次去递归地寻找他的祖先节点，并且在一路上都要注意更新，否则后期可能出现问题

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
//
//  9th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/5/11.
//
//

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x))

struct wid
{
    int v1;
    int v2;
    int width;
    bool chose;
};

wid a[1010];
int fa[100010];
int ran[100010];

void init()
{
    for (int i=0;i<=100010;i++)
    {
        fa[i] = i;
        ran[i] = 1;
    }
    return;
}

int find_fa(int x)
{
    if (fa[x]==x)
        return x;
    fa[x] = find_fa(fa[x]);
    return fa[x];
}

void unio(int x, int y)
{
    int fx = find_fa(x);
    int fy = find_fa(y);
    if (fx == fy)
        return;
    if (ran[fx]>ran[fy])
        fa[fy] = fx;
    else if(ran[fx]<ran[fy])
        fa[fx] = fy;
    else
    {
        fa[fy] = fx;
        ran[fx]++;
    }
    return;
}

bool cmp(wid x,wid y)
{
    return x.width<y.width;
}

void krus(int n, int m)
{
    int ans=0;
    init();
    sort(a+1, a+m+1, cmp);
    for (int i=1;i<=m;i++)
    {
        if (find_fa(a[i].v1)!=find_fa(a[i].v2))
        {
            unio(a[i].v1,a[i].v2);
            ans+=a[i].width;
            a[i].chose=true;
        }
    }
    cout << "Total cost:  " << ans << endl;
    cout << "The width we choose: " << endl;
    for (int i=1;i<=m;i++)
        if (a[i].chose)
            cout << a[i].v1 << " " << a[i].v2 << endl;
    
}

/*
 样例输入：
 9 14
 1 2 4
 2 3 8
 3 4 7
 4 5 9
 5 6 10
 6 7 2
 7 8 1
 8 9 7
 2 8 11
 3 9 2
 7 9 6
 3 6 4
 4 6 14
 1 8 8
*/
int main()
{
    int n,m;
    cout <<"Please input the number of vertex and edges" << endl;
    cin >> n >> m;
    for (int i=1;i<=m;i++)
    {
        cin >> a[i].v1 >> a[i].v2 >> a[i].width;
        a[i].chose=false;
    }
    krus(n, m);
    return 0;
}

载重问题(homework)

题目内容

现在有n个物品，告诉我们每个物品的重量。现在有两艘船，载重量分别是c1,c2。问我们能不能把东西都装上，如果能装上，怎么装

实现思路

我们首先知道，我们只要尽量装满第一艘，看剩下的第二艘能不能装就是可以。那么在实现第一艘尽量装满的过程中，我们使用了子集树作为这里的解题思路。也就是对每一步都根据取和不取往下dfs，并且适当进行剪枝操作。比如这里的两个剪枝条件是，1、如果取了之后大于容量了，就不取，如果这个不取，剩下的加上已有的也超不过先前已经得到的最大值，那么我们也不再往下找

实现细节

主要是各个下标不要弄错

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//
//  10th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/5/13.
//
//

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));

int n,c1,c2;
int w[100010];
int wn,wb;
int wr[100010];
bool pat[100010];
bool flag;

void backtrack(int level)
{
    if (level == n)
    {
        wb = max(wb,wn);
        return;
    }
    if (wn+w[level+1]<=c1)
    {
        wn += w[level+1];
        backtrack(level+1);
        wn -= w[level+1];
    }
    if (wn+wr[level+1]>wb)
        backtrack(level+1);
    return;
}

void backtrack_plan(int level)
{
    if (flag)
        return;
    if (level == n)
    {
        cout << "ship1:  ";
        for (int i=1;i<=n;i++)
            if (pat[i])
                cout << w[i] << " ";
        cout << endl;
        cout << "ship2:  ";
        for (int i=1;i<=n;i++)
            if (!pat[i])
                cout << w[i] << " ";
        cout << endl;
        flag = true;
        return;
    }
    pat[level+1] = false;
    if (wn+w[level+1]<=c1)
    {
        wn += w[level+1];
        pat[level+1] = true;
        backtrack_plan(level+1);
        pat[level+1] = false;
        wn -= w[level+1];
    }
    if (wn+wr[level+1]>=wb)
        backtrack_plan(level+1);
    return;
}

int main()
{
    /*
     样例输入：
        4 12 8
        8 6 2 3
     表示有4件物品，第一艘船载重c1=12，第二艘船载重c2=8，第二行是4个物品的质量
    */
    int sum = 0;
    flag = false;
    cin >> n >> c1 >> c2;
    for (int i=1;i<=n;i++)
    {
        cin >> w[i];
        sum += w[i];
    }
    wn = 0; wb = 0;
    wr[n] = w[n];
    for (int i=n-1;i>=1;i--)
        wr[i] = wr[i+1]+w[i];
    backtrack(0);
    wn = 0;
    if (c2<sum-wb)
        cout << "No such plan" << endl;
    else
    {
        backtrack_plan(0);
    }
}
Author: YihangBao
Link: https://roarboil.github.io/2020/04/24/cha4-1/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.