P14006

背包问题

难度小学算法入门递归背包 DFS

讨论统计 41通过 132提交 31.1%通过率旧版界面

时间限制 1 秒 内存限制 128 MB

题目描述

有 $N$ 件物品和一个容量为 $C$ 的背包。放入第i件物品耗费的空间是 $w_i$ ，得到的价值是 $v_i$ 。求解在不超过容量的前提下，将哪些物品装入背包可使价值总和最大。

第1行两个正整数，分别表示 $N$ 和 $C$ ，中间用一个空格隔开。

接着 $N$ 行，每行2个数字，其中第 $i$ 行的数字分别是物品的价值 $v_i$ 、物品耗费的空间是 $w_i$

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

样例 1

输入

输出

$1\leqN\leq30，1\leqC\leq 10^9 ，1\leq w_i \leq10^9，1\leq v_i \leq10^9$

上一题下一题