P2240. 部分背包问题

发表于 分类于 阅读次数： Waline： 本文字数： 189 阅读时长 ≈ 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
#include <bits/stdc++.h>

using namespace std;

const int LEN = 101;

struct Node
{
    int m_, v_;
} arr[LEN];

int main()
{
    int n, t;
    cin >> n >> t;
    for (int i = 0; i < n; ++i)
        cin >> arr[i].m_ >> arr[i].v_;
    sort(arr, arr + n, [](Node a, Node b) -> bool
         { return a.v_ * b.m_ > b.v_ * a.m_; });
    double ans = 0;
    for (int i = 0; i < n; ++i)
    {
        if (t >= arr[i].m_)
        {
            ans += arr[i].v_;
            t -= arr[i].m_;
        }
        else
        {
            ans += 1.0 * arr[i].v_ * t / arr[i].m_;
            break;
        }
    }
    cout << fixed << setprecision(2) << ans;
    return 0;
}

思路

价值尽可能多，且金币可以再分；所以不需要DP，典型的贪心算法

每次选单位价格最大的就行，直到该种金币用完再继续下一个

注意，为了避免除法带来的精度误差，转用乘法进行比较 \[ \frac{v_1}{m_1}>\frac{v_2}{m_2}\rightarrow v_1\cdot m_2>m_1\cdot v_2 \]