g6-08014. 双背包·三去向 · 林老师的题库

题目描述

小杨有两个背包要分装：有 $n$ 件物品，第 $i$ 件重 $w_{i}$ 、价值 $v_{i}$ 。每件物品有三种去向：放进背包 A（容量 $V_{A}$ ）、放进背包 B（容量 $V_{B}$ ），或者直接丢弃，每件最多选一种去向。求两个背包中物品的总价值最大是多少。

第一行三个整数 $n, V_{A}, V_{B}$ 。

接下来 $n$ 行，每行两个整数 $w_{i}, v_{i}$ 。

一行一个整数，表示最大总价值。

2 4 4
3 2
3 2

两件分放 A、B 两个背包。

$1 \leq n \leq 40$ ， $1 \leq V_{A}, V_{B} \leq 150$ ， $1 \leq w_{i}, v_{i} \leq 100$ 。