【题目来源】
学而思编程：小明的U盘
【题目描述】
在 2202 年的某一天，小明得到了一个高端 U 盘。
但是小明发现这个 U 盘有一些问题：
这个 U 盘的传输接口大小是 \(L\)，只能传输大小不超过 \(L\) 的文件。
这个 U 盘容量是 \(S\)，一共只能装不超过 \(S\) 的文件。
但是他要备份的资料却有很多，你只能备份其中的一部分。
共有 \(n\) 个文件，第 \(i\) 个文件的大小和价值为 \(w_i,v_i\)。小明很快发现他不可能把所有文件装进优盘，好在这是一个高端的 U 盘，他可以花钱升级接口大小、或者升级容量。每花 \(1\) 元可以将接口大小增加 \(1\)，每花 \(1\) 元可以将 U 盘容量增加 \(1\)。
注意：你的文件不能被分割（你只能把一个文件整个的传输进去，并储存在U盘中），你放在 U 盘中文件的总大小不能超过 U 盘容量。
现在问题来了：小明只有 \(m\) 元，他想知道，他最多可能将多大价值的文件放入 U 盘中。
【输入】
第 \(1\) 行，\(4\) 个正整数 \(n,m,L,S\)。
第 \(2\) 行，\(n\) 个正整数 \(w_1,w_2,⋯ ,w_n\)。
第 \(3\) 行，\(n\) 个正整数 \(v_1,v_2,⋯ ,v_n\)。
【输出】
\(1\) 个整数，最多可以放入 U 盘的文件总价值。
【输入样例】
5 9 4 4
6 9 9 5 6
8 7 9 1 5
【输出样例】
9
【核心思想】
-
问题分析：给定 \(n\) 个文件（大小 \(w_i\)，价值 \(v_i\)），U盘初始接口大小 \(L\)、容量 \(S\)，预算 \(m\) 元。每花1元可将接口或容量增加1。文件大小必须同时满足：不超过接口大小（才能传输）和不超过U盘容量（才能存储）。可以选择升级接口使某个大文件能够传输，求在预算内能装入的最大总价值。这是一个01背包变体问题，关键在于枚举哪个文件享受接口升级优惠。
-
算法选择：
- 01背包：
dp[i][j]表示前 \(i\) 个文件，花费不超过 \(j\) 的最大价值 - 枚举优惠券使用：排序后枚举哪个文件使用接口升级
- 01背包：
-
关键步骤：
- 按大小排序：将文件按 \(w_i\) 从小到大排序，保证枚举时前面文件都能通过当前接口
- 01背包DP：总可用资金 = 初始容量 \(S\) + 预算 \(m\)
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])（选或不选第 \(i\) 个文件）
- 枚举升级使用：对于排序后的第 \(i\) 个文件：
- 升级接口后的实际大小：
cost = max(w[i] - L, 0)（升级后大小为 \(L\)，原大小 \(w[i]\) 需要升级 \(w[i]-L\)） - 剩余容量给其他文件：
S + m - cost - 答案更新：
ans = max(ans, dp[i][S + m - cost])
- 升级接口后的实际大小：
-
时间/空间复杂度：
- 时间复杂度：\(O(n \times (S+m) + n \log n)\)，排序 \(O(n \log n)\)，背包 \(O(n \times (S+m))\)
- 空间复杂度：\(O(n \times (S+m))\)
-
01背包变体（带优惠券抵扣）的核心思想：
- 排序预处理：按文件大小排序，确保枚举时前面文件都能通过当前接口大小
- 枚举策略：枚举哪个文件使用接口升级优惠，其余文件使用普通容量
- 费用计算：升级接口后的实际占用 =
max(原大小 - 接口大小, 0) - 容量分配：总资源 = 初始容量 + 预算，分配给升级文件和普通文件
- 适用于带单一优惠选择的背包问题
【算法标签】
01背包
【代码详解】
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int n, m, l, s, dp[N][20005], ans; // dp: 背包DP数组, ans: 最终答案
struct node
{int w, v; // w: 原价, v: 价值
} a[N];// 按原价从小到大排序
bool cmp(node x, node y)
{return x.w < y.w;
}int main()
{cin >> n >> m >> l >> s;for (int i = 1; i <= n; i++){cin >> a[i].w; // 读取原价}for (int i = 1; i <= n; i++){cin >> a[i].v; // 读取价值}sort(a + 1, a + n + 1, cmp);// 0/1背包：计算前i个物品，花费不超过j的最大价值for (int i = 1; i <= n; i++){for (int j = 1; j <= s + m; j++) // 总可用资金 = 初始资金s + 优惠券价值m{dp[i][j] = dp[i - 1][j]; // 不选第i个物品if (j >= a[i].w){// 选第i个物品dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i].w] + a[i].v);}}}// 枚举使用优惠券购买的商品ifor (int i = 1; i <= n; i++){// 使用优惠券后的实际花费：原价 - 优惠券价值l，但不能为负int cost = max(a[i].w - l, 0);ans = max(ans, dp[i][s + m - cost]);}cout << ans;return 0;
}
【运行结果】
5 9 4 4
6 9 9 5 6
8 7 9 1 5
9