‹ 上一题 下一题 ›

g6-08023. 0/1 与分数对照 未做

1000 ms 256 MB 测试点 ? 6级·0/1背包GESP-6贪心边界背包与贪心的边界

题目描述

件物品,第 件重量 、价值 ,容量 。分别计算:

  1. 每件只能整个选或不选(标准 背包)的最大价值;
  2. 每件可以切分(分数背包)的最大价值(整数部分)。

一行输出两个整数: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。

数据范围

,,。

输入
输出

            
答案