Charm Bracelet S（01背包问题）

ID: 98

传统题

1000ms

256MiB

难度: 10

上传者:

题目描述

有 $N$ 件物品和一个容量为 $M$ 的背包。第 $i$ 件物品的重量是 $W_i$ ，价值是 $D_i$ 。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

第一行：物品个数 $N$ 和背包大小 $M$ 。

第二行至第 $N+1$ 行：第 $i$ 个物品的重量 $W_i$ 和价值 $D_i$ 。

输出一行最大价值。