#11316. 01背包问题

内存限制:512 MiB 时间限制:1000 ms 输入文件: back.in 输出文件: back.out
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

N 件物品,每件物品有一个重量和一个价值,分别记为 W_1 ,W_2 ,…,W_n C_1 ,C_2 ,…,C_n

现在有一个背包,其最大承重为 M 。要从 N 件物品种任取若干件,要求:

(1) 重量之和小于或等于 M

(2) 价值之和最大。

输入格式

第 1 行: 2 个整数,表示 N M

第 2 行: N 个整数,表示每一个物品的重量,

第 3 行: N 个整数,表示每一个物品的价值。

输出格式

一个数,表示符合背包承重的最大价值。

样例

【输入样例】

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

【输出样例】

334

数据范围与提示

80% 数据: 1≤N≤20

100% 数据: 1≤N≤100 1≤M≤10^6 1≤W_i ≤10^5 1≤C_i ≤10^8

【提示】“01 背包”,即每件物品只有不取和取两种情况,对应着二进制中的 0 和 1。01 背包有多种解决算法,

(1)如果采用二进制穷举思想,即从 000…00 穷举到 111…11。

(2)二进制枚举可能会超时,可采用动态规划算法。