#P1246. 背包问题

    ID: 256 传统题 1000ms 512MiB 尝试: 69 已通过: 22 难度: 6 上传者: 标签>CF2100提高二分答案回溯搜索对称性剪枝可行性剪枝搜索顺序优化交换论证一维前缀和

背包问题

题目描述

有 NN 个物品,每个物品有一定的重量,有 MM 个袋子,它们有一定的承重,现在问使用这 MM 个袋子,最多可以带走多少个物品.

输入格式

第一行一个数 MM,以下 MM 行每行一个数,为每个袋子的承重 BiB_i 接下来一个数字 NN,以下 NN 行每行一个数,为每个物品的重量 AiA_i 100%数据 N≤5000,M≤300,Ai≤128N\leq 5000,M\leq 300,A_i\leq128

输出格式

仅一个数,为最多可以带走多少物品.

3
22
16
2
7
8
4
2
10
8
9
6
6