有 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)二进制枚举可能会超时,可采用动态规划算法。