A3636 | $【穷举】0-1 背包问题$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

有 n 件物品，每件物品有一个重量和一个价值，分别记为 W1 ，W2 ，\dots，Wn 和 C1 ，C2 ，\dots，Cn 。现在有一个背包，其容量为 WK，要从 n 件物品种任取若干件，要求： （1） 重量之和小于或等于 WK。 （2） 价值之和最大。

第 1 行 2 个整数，表示 n和WK，1 \leq n \leq 20，1 \leq WK \leq 800005 。 第 2 行 n 个整数，表示每一个物品的重量，1 \leq Wi \leq 10^4 。 第 3 行 n 个整数，表示每一个物品的价值，1 \leq Ci \leq 10^8 。

一行一个数，表示符合背包容量的最大价值。

输入 #1

8 200
79 58 86 11 28 62 15 68
83 14 54 79 72 52 48 62

输出 #1

C++ 编辑器

输入

输出