AT_abc275_g [ABC275G] Infinite Knapsack

题目描述

有 $N$ 种物品，每种物品都有无限多个。第 $i$ 种物品的重量为 $A_i$，体积为 $B_i$，价值为 $C_i$。

等级为 $X$ 的高桥君可以选择若干物品，使得所选物品的总重量不超过 $X$，总体积也不超过 $X$。在满足条件的情况下，同一种物品可以选择任意多个，也可以有不选择的种类。

设等级为 $X$ 的高桥君所能获得的最大总价值为 $f(X)$。可以证明极限 $\displaystyle\lim_{X\to\infty}\ \frac{f(X)}{X}$ 存在。请计算该值。

输入格式

输入通过标准输入给出，格式如下：

$N$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_N$ $B_N$ $C_N$

输出格式

请输出答案。如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

输入输出样例 #1

输入 #1

2
100000000 200000000 100000000
200000000 100000000 100000000

输出 #1

0.6666666666666667

输入输出样例 #2

输入 #2

1
500000000 300000000 123456789

输出 #2

0.2469135780000000

说明/提示

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $10^8 \leq A_i, B_i, C_i \leq 10^9$
• 输入均为整数

样例解释 1

当 $X=300000000$ 时，高桥君可以选择若干物品，使得总重量和总体积都不超过 $300000000$。一种选择方式是各选 $1$ 个第 $1$ 种和第 $2$ 种物品，此时总价值为 $100000000+100000000=200000000$，这是可以达到的最大价值，因此 $\dfrac{f(300000000)}{300000000}=\dfrac{2}{3}$。对于本输入，也可以证明极限 $\displaystyle\lim_{X\to\infty}\ \dfrac{f(X)}{X}$ 也等于 $\dfrac{2}{3}$，所以答案为 $0.6666666\ldots$。

由 ChatGPT 4.1 翻译