算法

贪心入门-部分背包问题

题目

题目来自洛谷：https://www.luogu.com.cn/problem/P2240，是一道入门贪心题。

题解

因为所有金币可以随意分割，所以可以对金币单位价值进行排序按价值比高的先装进背包来得到最优选择。

首先对输入数据进行分析，对于每一堆金币都有总重量和总价值两个量，可以将这两个量组成结构体：

1
2
3
4

struct coin
{
    int m, v;
} a[105];

m 为总质量，v 为总价值。
这个结构体有什么好处呢，观察用例会发现，每一堆金币的单位价格的不一样的，通过结构化每一堆金币可以大大简化后续排序金币堆的复杂度。

我们可以创建一个比较函数用于后续给 sort() 传递的函数指针：

1
2
3
4

int cmp(coin x, coin y)
{
    return x.v * y.m > y.v * x.m;
}

这里使用到了性价比比较的方式，对于两堆金币，其的性价比可以为： $\frac{总价值}{总质量}$ 而假设比较有: $\frac{A.总价值}{B.总质量}>\frac{B.总价值}{B.总质量}$
可以移项变成: $A.总价值 \times B.总质量 > B.总价值 \times A.总质量$
这就是该比较函数的数学意义。
在之后我们的排序使用 sort 函数时就将该比较函数传入作为比较的办法：

1

sort(a, a + n, cmp);

先放上 main 函数的内容：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

int main()
{
    int n, t, remain, i;
    double res = 0.0;
    scanf("%d%d", &n, &t);
    remain = t;
    for (i = 0; i < n; i++)
        scanf("%d%d", &a[i].m, &a[i].v);

    sort(a, a + n, cmp);
    for (i = 0; i < n; i++)
    {
        if (a[i].m > remain)
            break;
        remain -= a[i].m;
        res += a[i].v;
    }
    if (i < n)
        res += (double)remain / a[i].m * a[i].v;
    printf("%.2lf", res);
}

基本都是按题意来，通过排序，从最有价值的金币堆开始装入，要考虑需要分割金币堆的情况。后面的逻辑比较简单。

AC 代码

 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

#include <algorithm>
#include <cstdio>
using namespace std;

struct coin
{
    int m, v;
} a[105];

// 性价比排序
int cmp(coin x, coin y)
{
    return x.v * y.m > y.v * x.m;
}

int main()
{
    int n, t, remain, i;
    double res = 0.0;
    scanf("%d%d", &n, &t);
    remain = t;
    for (i = 0; i < n; i++)
        scanf("%d%d", &a[i].m, &a[i].v);

    sort(a, a + n, cmp);
    for (i = 0; i < n; i++)
    {
        if (a[i].m > remain)
            break;
        remain -= a[i].m;
        res += a[i].v;
    }
    if (i < n)
        res += (double)remain / a[i].m * a[i].v;
    printf("%.2lf", res);
}

参考资料

  1. 洛谷 深入浅出程序设计竞赛（基础篇） 高等教育出版社
萌ICP备20241614号