A3636. 【穷举】0-1 背包问题
编程题
入门
知识点
题目描述
有 n 件物品，每件物品有一个重量和一个价值，分别记为 W1 ，W2 ，…，Wn 和 C1 ，C2 ，…，Cn 。现在有一个背包，其容量为 WK，要从 n 件物品种任取若干件，要求：
（1） 重量之和小于或等于 WK。
（2） 价值之和最大。
（1） 重量之和小于或等于 WK。
（2） 价值之和最大。
输入格式
第 1 行 2 个整数，表示 n和WK，1 ≤ n ≤ 20，1 ≤ WK ≤ 800005 。
第 2 行 n 个整数，表示每一个物品的重量，1 ≤ Wi ≤ 10^4 。
第 3 行 n 个整数，表示每一个物品的价值，1 ≤ Ci ≤ 10^8 。
第 2 行 n 个整数，表示每一个物品的重量，1 ≤ Wi ≤ 10^4 。
第 3 行 n 个整数，表示每一个物品的价值，1 ≤ Ci ≤ 10^8 。
输出格式
一行一个数，表示符合背包容量的最大价值。
输入输出样例
输入 #1
8 200 79 58 86 11 28 62 15 68 83 14 54 79 72 52 48 62
输出 #1
334