j01668. 至少型体积 · 林老师的题库

题目描述

小 P 要往背包里装东西，背包的目标是「装满」：只要装进去的总体积不少于 $V$ 就算达标（超出的部分不做要求，也不额外加分）。

货架上共有 $n$ 件物品，第 $i$ 件的体积是 $w_{i}$ 、价值是 $v_{i}$ ，每件最多装一次。

在总体积至少为 $V$ 的前提下，请计算能装入物品的最大价值总和。数据保证所有物品的总体积不少于 $V$ （一定可以达标）。

第一行两个整数 $n$ 和 $V$ 。

接下来 $n$ 行，每行两个整数 $w_{i}$ 和 $v_{i}$ ，依次表示第 $i$ 件物品的体积与价值。

一行一个整数，表示总体积不少于 $V$ 时的最大价值总和。

输入

输出

三件全拿：总体积 $2 + 3 + 1 = 6 \geq 4$ 达标，价值 $5 + 1 + 2 = 8$ 。

只拿第 1 件（体积 $2$ ）或只拿第 2 件（体积 $3$ ）都不到 $4$ ，不达标；拿第 1、2 件价值只有 $6$ 。