【深基12.例1】部分背包问题

题意

有若干堆金币，每堆有重量和价值。金币可以任意分割，背包容量为 T，求最多能拿走多少价值。

思路

因为金币可以分割，所以这是部分背包。

每堆金币只需要看单位价值：

text

1value / weight

按单位价值从高到低排序，能整堆拿就整堆拿，装不下时拿剩余容量对应的一部分，然后结束。

Python 知识

items.append((value / weight, weight, value)) 把排序关键字放在元组第一项。
items.sort(reverse=True) 按单位价值降序排列。
print(f"{answer:.2f}") 输出两位小数。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20n, capacity = map(int, input().split())

items = []
for _ in range(n):
    weight, value = map(int, input().split())
    items.append((value / weight, weight, value))

items.sort(reverse=True)

answer = 0.0
remaining = capacity

for unit_value, weight, value in items:
    if remaining == 0:
        break
    take = min(remaining, weight)
    answer += take * unit_value
    remaining -= take

print(f"{answer:.2f}")

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

/* P2240 部分背包问题 */
/* 按单位价值从高到低排序，能整堆拿就整堆拿，装不下时拿一部分然后结束。 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, capacity;
// 每堆金币：重量、价值、单位价值
int w[MAXN], v[MAXN];
double r[MAXN]; // 单位价值 = v / w
int idx[MAXN];  // 排序用的索引

// 按单位价值降序排列
bool cmp(int a, int b) {
    return r[a] > r[b];
}

int main() {
    cin >> n >> capacity;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
        r[i] = (double)v[i] / w[i];
        idx[i] = i;
    }

    // 按单位价值降序排序
    sort(idx + 1, idx + n + 1, cmp);

    double ans = 0.0;
    int remain = capacity;
    for (int i = 1; i <= n && remain > 0; i++) {
        int id = idx[i];
        // 能拿多少拿多少
        int take = min(remain, w[id]);
        ans += take * r[id];
        remain -= take;
    }

    printf("%.2f\n", ans);
    return 0;
}

复杂度

排序时间复杂度为 $O(N\log N)$ ，扫描为 $O(N)$ ，空间复杂度为 $O(N)$ 。

总结

部分背包和 0/1 背包不同：能拆分时，单位价值最高的先拿一定不亏。

【深基12.例1】部分背包问题

目录

题意

思路

Python 知识

代码

复杂度

总结