yyy2015c01 的 U 盘

GitHub跳转原题关系图Canvas 关系图返回列表

二分最小文件大小限制L，每次check用0/1背包判断在容量S限制下能否装下价值≥p的文件。

OJ: luogu

题目 ID: P2370

难度:普及+/提高-

标签:动态规划01背包二分答案

日期: 2026-08-08 23:13

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

有 nn 个文件，每个文件有大小 WiW_i 和价值 ViV_i。U盘容量为 SS，传输接口只能传输大小不超过 LL 的文件。文件不能被分割，要求选出总大小不超过 SS 的文件，使总价值至少为 pp。

问在满足条件的前提下，最小的接口大小 LL 是多少？无解输出 No Solution!。

1≤n,Wi,S≤1031\le n,W_i,S\le 10^3，1≤Vi≤1061\le V_i\le 10^6，1≤p≤1091\le p\le 10^9。

思路

一句话本质：“最小的最大文件大小” 是典型的二分答案模型：二分 LL，每次用 0/1 背包 check 在只选 Wi≤LW_i\le L 的文件时能否装下至少 pp 价值。

题目有多个变量纠缠在一起——文件大小限制、容量限制、价值目标，应该如何拆解？

先抓住主要矛盾：如果我们确定了接口大小 LL，那么"哪些文件可以传输"就明确了（只有 Wi≤LW_i\le L 的可以用）。此时问题退化为普通 0/1 背包：容量 SS，物品重量为 WiW_i，价值为 ViV_i，问最大价值能否 ≥p\ge p。

既然 LL 确定后问题就简单，如何找到最小的可行 LL？

LL 越大，可用的文件越多，越容易达到价值目标。所以"能否满足条件"关于 LL 是单调的：如果 LL 可行，更大的 LL 也一定可行。单调性意味着可以用二分答案。

二分范围 [1,max⁡Wi][1, \max W_i]，每次取中点 midmid，调用 check(mid) 判断是否可行。可行就尝试更小的 LL（r = mid-1），否则加大 LL（l = mid+1）。

check(L) 内部怎么做？

遍历所有物品，跳过 Wi>LW_i > L 的文件（这些文件即使想选也传输不了）。对剩余文件做标准 0/1 背包：dp[j]dp[j] 表示容量 jj 能获得的最大价值，倒序转移：

dp[j]=max⁡(dp[j],  dp[j−Wi]+Vi)dp[j] = \max(dp[j],\; dp[j-W_i] + V_i)

最后检查是否存在某个 j≤Sj\le S 满足 dp[j]≥pdp[j]\ge p，存在则 LL 可行。

二分的边界如何取？

如果 max⁡Wi\max W_i 都不行，说明即使放开所有文件也无法达到 pp 价值，无解。二分结束时若 ans == -1 就输出 No Solution!。

代码

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

typedef long long ll;

const int MAXS = 1005;

int n;
ll p;
int S;
int w[MAXS];
int v[MAXS];
// dp[j] 是 check() 函数内的局部 DP 数组，表示用容量 j 能获得的最大价值。
ll dp[MAXS];

// 判断在文件大小不超过 L 的情况下，能否装下价值 ≥ p 的文件。
bool check(int L) {
    fill(dp, dp + S + 1, 0);
    for (int i = 1; i <= n; i++) {
        if (w[i] > L) continue;
        for (int j = S; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    for (int j = 0; j <= S; j++) {
        if (dp[j] >= p) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> p >> S;

    int max_w = 0;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
        max_w = max(max_w, w[i]);
    }

    // 二分答案：找最小的文件大小限制 L 使得可以装下 ≥ p 的价值。
    int l = 1, r = max_w, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    if (ans == -1) {
        cout << "No Solution!" << '\n';
    } else {
        cout << ans << '\n';
    }
    return 0;
}

复杂度

  • 二分次数：O(log⁡max⁡Wi)O(\log \max W_i)
  • 每次 check：O(n⋅S)O(n\cdot S)
  • 总复杂度：O(n⋅S⋅log⁡W)O(n\cdot S \cdot \log W)，在 n,S≤1000n,S\le 1000 下可行
  • 空间复杂度：O(S)O(S)

总结

这道题的真正难点不是背包本身，而是把"最小化接口大小"翻译成二分答案 + 可行性验证。当答案有单调性且验证相对简单时，二分答案是最自然的降维思路：把"求最优 L"拆成"判断某个 L 是否可行"。