0/1背包[2]
测试数据来自 system/1124
作业已超过截止时间,您无法递交本题目。
时间限制:1秒 内存限制:256M
【问题描述】
有 \(n\) 个物品,物品i的体积为 \(v[i]\)。现有一个容量为 \(C\) 背包,请计算该背包能装载物品的最大数量。注意:每个物品要么全装入,要么不装入,不能只装一部分。
【输入格式】
第 1 行是 \(n\) 和 \(C\);
接下来一行有 \(n\) 个整数,第 \(i\) 个数表示物品的体积 \(v[i]\)。
【输出格式】
输出一个整数,表示能装入的最大物品数量。
【输入输出样例】
Input
5 10
1 3 2 4 6
Output
4
【数据限制】
\(0<n<=50000\)
\(0<v[i],C<=10^9\)
【来源】
Mr.he