题目描述
件物品,第 件重量 、价值 ,容量 。分别计算:
- 每件只能整个选或不选(标准 背包)的最大价值;
- 每件可以切分(分数背包)的最大价值(整数部分)。
一行输出两个整数:0/1 值、分数值(分数值不低于 0/1 值)。
输入格式
第一行两个整数 。
接下来 行,每行两个整数 。
输出格式
一行两个整数,用空格分隔。
样例
输入 1
3 10
6 60
5 45
5 45
输出 1
90 96
0/1:选第 2、3 件得 90。分数:第 1 件全拿(60),剩 4 容量切第 2 件的 得 36,共 96。
数据范围
,,。