回溯暴力解法

这道题的正解是 $动态规划$，但是我们用朴素解法 $回溯$ 也能在考试时拿到一定的分数。

必须按编号 $1\sim n$ 依次决定每件货物装或不装。占用体积达到 $T$ 之后，再装的货物按 $\lfloor v_i/2\rfloor$ 计入，且占用不能超过 $W$。目标是最大货值，允许一件都不装。

朴素做法：从第 $0$ 件开始做「不装 / 装」的回溯。

1. 走到第 $n$ 件时，用当前货值更新答案。

题目内容

仓库按工单编号依次处理 $n$ 件货物，编号 $1\sim n$。叉车载重上限为 $W$。每件货物有占用体积 $v_i$ 和货值 $w_i$，每件至多装一次，也可以不装。必须按编号从小到大决定：对于当前这件货物，要么装上，要么永久跳过，不能回头再装已经跳过的货物。

装车优惠：当叉车上已经占用的体积达到阈值 $T$ 之后，再装的货物按优惠体积计入，优惠体积为 $\lfloor v_i/2\rfloor$（可以为 $0$）。一件货物按“决定装它的那一刻”是否已经触发优惠来计体积：

• 尚未触发：占用 $v_i$。装上之后若占用体积第一次达到或超过 $T$，此后才算触发。
• 已经触发：占用 $\lfloor v_i/2\rfloor$。

占用体积始终不能超过 $W$。请给出在该装车顺序规则下能得到的最大货值。允许一件都不装，此时答案为 $0$。

输入描述

第一行三个整数 $n$、$W$、$T$。

接下来 $n$ 行，第 $i$ 行两个整数 $v_i$、$w_i$，按工单编号 $1\sim n$ 给出。

约束

$1 \le n \le 100$

$1 \le W \le 5000$

$1 \le T \le 5000$

$1 \le v_i \le 5000$

$1 \le w_i \le 10^6$

输出描述

输出一个整数，即最大货值。

样例1

输入

3 10 5
6 10
4 9
5 8

输出

27

说明

三件都装：先装体积 $6$（占用 $6$，已达阈值），再装体积 $4$（优惠占用 $2$），再装体积 $5$（优惠占用 $2$），总占用 $10$，货值 $10+9+8=27$。

样例2

输入

3 8 4
5 1
4 100
4 100

输出

200

说明

若先装第一件（占用 $5$），后面两件优惠后各占 $2$，总占用 $9$，超过 $8$，只能再装其中一件，货值至多 $101$。跳过第一件：先装第二件（占用 $4$，触发优惠），再装第三件（占用 $2$），总占用 $6$，货值 $200$。