0-1 Knapsack · GESP 6级 每日一题 Day01

题目描述

有 $n$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的重量是 $w_i$，价值是 $v_i$。每件物品只能选或不选。

请你求出将哪些物品装入背包可使这些物品的价值总和最大，输出最大总价值。

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

接下来 $n$ 行，每行两个整数 $w_i, v_i$。

一行一个整数，表示能装下的最大总价值。

• $1 \le n \le 1000$
• $1 \le V \le 10000$
• $1 \le w_i \le V$
• $1 \le v_i \le 1000$